Description
已知多项式方程：
a0+a1*x+a2*x^2+…+an*x^n=0
求这个方程在[1,m]内的整数解（n和m均为正整数）。
Input
第一行包含2个整数n、m，每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数，依次为a0,a1,a2,…,an。
Output
第一行输出方程在[1,m]内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1,m]内的一个整数解。
Sample Input
2 10
2
-3
1
2
-3
1
Sample Output
2
1
2
1
2
HINT
对于100%的数据，0<n≤100，|ai|≤1010000，an≠0，m≤1000000。
Solution
用hash来做，交了好多好多次终于AC了！
Tip: BZOJ上的数据是加强过的，还有|ai|<=10^10000。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<iostream> #include<cstdio> #define ll long long using namespace std; const int g[5]={18503,20143,19001,27551,17011}; int n,m,a[105][5],f[30000][5],answer[1000010]; void read(int i) { char ch=getchar(); bool flag=false; while (ch<'0'||ch>'9') { if (ch=='-') flag=true;ch=getchar();} while (ch>='0'&&ch<='9') { for (int j=0;j<5;j++) a[i][j]=(a[i][j]*10+ch-'0')%g[j]; ch=getchar(); } if (flag) for (int j=0;j<5;j++) a[i][j]=(-a[i][j]+g[j])%g[j]; } int calc(int x,int j,int mo) { int ans=a[0][j],t=x; for (int i=1;i<=n;i++) { ans=(ans+a[i][j]*t)%mo; t=t*x%mo; } return ans; } int main() { scanf("%d%d",&n,&m); for (int i=0;i<=n;i++) read(i); for (int i=0;i<=4;i++) for (int j=0;j<g[i];j++) f[j][i]=calc(j,i,g[i]); int ans=0; for (int i=1;i<=m;i++) { bool flag=true; for (int j=0;j<=4;j++) if (f[i%g[j]][j]!=0) { flag=false;break;} if (flag) answer[++ans]=i; } printf("%d\n",ans); for (int i=1;i<=ans;i++) printf("%d\n",answer[i]); return 0; } |
