题目描述
已知多项式方程：
a0+a1x+a2x^2+..+anx^n=0
求这个方程在[1, m ] 内的整数解（n 和m 均为正整数）
输入输出格式
输入格式：
输入文件名为equation .in。
输入共n + 2 行。
第一行包含2 个整数n 、m ，每两个整数之间用一个空格隔开。
接下来的n+1 行每行包含一个整数，依次为a0,a1,a2..an
输出格式：
输出文件名为equation .out 。
第一行输出方程在[1, m ] 内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m ] 内的一个整数解。
输入输出样例
输入样例#1：
2 10 1 -2 1
输出样例#1：
1 1
输入样例#2：
2 10 2 -3 1
输出样例#2：
2 1 2
输入样例#3：
2 10 1 3 2
输出样例#3：
0
说明
30%:0<n<=2,|ai|<=100,an!=0,m<100
50%:0<n<=100,|ai|<=10^100,an!=0,m<100
70%:0<n<=100,|ai|<=10^10000,an!=0,m<10000
100%:0<n<=100,|ai|<=10^10000,an!=0,m<1000000
代码
不会写，水过了30分，QAQ1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #define ll long long 6 using namespace std; 7 8 ll v[555],a[555],ans,N,M,p; 9 10 ll pow(ll x,ll n){ 11 ll ans=1; 12 while(n){ 13 if(n&1) ans=ans*x; 14 x=x*x; 15 n>>=1; 16 } 17 return ans; 18 } 19 20 ll cc(ll x){ 21 ll ans=a[0]; 22 for(ll i=1;i<=N;i++){ 23 ans+=a[i]*pow(x,i); 24 } 25 if(ans==0) { 26 v[++p]=x; 27 return 1; 28 } 29 return 0; 30 } 31 32 int main(){ 33 // freopen("equation.in","r",stdin); 34 // freopen("equation.out","w",stdout); 35 36 37 scanf("%lld%lld",&N,&M); 38 for(ll i=0;i<=N;i++){ 39 scanf("%lld",&a[i]); 40 } 41 42 for(ll i=1;i<=M;i++){ 43 if(cc(i)) ++ans; 44 } 45 46 printf("%lld ",ans); 47 for(ll i=1;i<=p;i++) printf("%lld ",v[i]); 48 49 return 0; 50 }转载：
没有c++题解，果断来一发
50%数据：
从1到m暴力枚举答案，然后通过高精度进行计算。
70%数据：
仍然从1到m暴力枚举答案，但是我们不再进行高精度运算，而是模质数。为了减小冲突的几率，我们可以多选几个数字去模。这样时间复杂度是O(nmprime)，其中prime是选取的质数的数量，选四五个就行。
100%数据：
如果我们模的数字是k。左边式子带入x和带入x+k是没有区别的。如果我们把质数k取得小一些，这样x就不用试1~m，而是试1~k。这样复杂度就变成了O(nkprime)，如果k取10^4左右就完全没有问题。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdlib> 6 using namespace std; 7 #define PROB "equation" 8 #define MAXN 1100001 9 ifdef WIN32 10 11 #define LL "%I64d" 12 #else 13 #define LL "%lld" 14 #endif 15 typedef long long qword; 16 const int mod[5] = 17 {22861,22871,22877,22901,22907 18 }; 19 int a[11][110]; 20 bool ok[MAXN]; 21 bool ok2[5][30000]; 22 char s[10010]; 23 int n,m; 24 void work(); 25 int main() 26 { 27 int ii,i,j, k; 28 int x; 29 scanf("%d%d ",&n,&m); 30 int ll = 4; 31 for (ii=0;ii<=n;ii++) 32 { 33 // scanf("%s", s); 34 fgets(s,sizeof(s),stdin); 35 int l = strlen(s)-1; 36 if((s[l-1]<'0' || s[l-1]>'9') && s[l-1]!='-')l--; 37 for(int j = 0; j < ll; j ++){ 38 int pmod = mod[j]; 39 a[j][ii] =0; 40 x=1; 41 k=0; 42 if (s[k]=='-')k++,x=-x; 43 else if (s[k]=='+')k++; 44 for (;k<l;k++) 45 { 46 a[j][ii]=(a[j][ii]*10+s[k]-'0')%pmod; 47 } 48 a[j][ii]=a[j][ii]*x%pmod; 49 if(a[j][ii] < 0) 50 a[j][ii] += pmod; 51 } 52 } 53 memset(ok,1,sizeof(ok)); 54 memset(ok2,1,sizeof(ok2)); 55 int pmod; 56 int ans; 57 for (ii=0;ii<ll;ii++) 58 { 59 pmod=mod[ii]; 60 for (i=0;i<pmod;i++) 61 { 62 ans=0; 63 for (j=n;j>=0;j--) 64 { 65 ans=(ans * i + a[ii][j])%pmod; 66 } 67 if (ans) 68 { 69 ok2[ii][i]=false; 70 } 71 } 72 } 73 int cnt = 0; 74 for (int i=1;i<=m && cnt <= n;i++) 75 { 76 for (int j=0;j<ll;j++) 77 { 78 if (!ok2[j][i%mod[j]]){ 79 ok[i]=false; 80 break; 81 } 82 } 83 if(ok[i]) 84 ++ cnt; 85 } 86 printf("%d ",cnt); 87 for (i=1;i<=m;i++) 88 if (ok[i]) 89 printf("%d ",i); 90 return 0; 91 }
