NOIP2014 解方程

题目大意 已知多项式方程：a0+a1x+a2x^2+..+anx^n=0 求这个方程在[1, m ] 内的整数解（n 和m 均为正整数） 0<n<=100,|ai|<=10^10000,an!=0,m<1000000 Solution 首先要知道的是高次方程无求根公式，所以解这个方程没有公式，套公式只能过30%的数据 一种方法是枚举1到m的正整数，判断行不行。 若用高精度则只能能拿50分，那如何优化呢？取模！ 设f(x)=a0+a1*x+a2*x^2+..+an*x^n 若f(x)=0则f(x) mod p=0（p为任意非0实数） 随意试几个p，若f(x) mod p都是0，那x很有可能就是方程的解 但有几点要注意： 1。p最好是质数 2。p试得越多，p越大正确率越高，但也会慢一点点，根据实际情况自己调节 最后用秦九韶来计算 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int p=10007,q=100000007; int n,m,i,cnt,ans[1000003],v[p],y; ll a[103],b[103],aa,bb; char c; inline char gc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read(){ int x=0,fl=1;char ch=gc(); for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1; for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48); return x*fl; } inline bool f(int p,int M,ll *t){//把p代入方程，判断模M是否为0 ll x=t[n]; for (int i=n-1;i>=0;i--) x=(x*p+t[i])%M; return x==0; } inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);} inline void wln(int a){wri(a);puts("");} int main(){ n=read();m=read(); for (i=0;i<=n;i++){//读入优化 aa=0,bb=0; for (c=gc(),y=0;c<48 || 57<c;c=gc()) if (c=='-') y=1; for (;48<=c && c<=57;c=gc()) aa=((aa<<3)+(aa<<1)+(c^48))%p,bb=((bb<<3)+(bb<<1)+(c^48))%q; a[i]=y?p-aa:aa; b[i]=y?q-bb:bb; } for (i=0;i<p;i++) if (f(i,p,a)) v[i]=1; for (i=1;i<=m;i++) if (v[i%p] && f(i,q,b)) ans[cnt++]=i; wln(cnt); for (i=0;i<cnt;i++) wln(ans[i]); } ```