https://daniu.luogu.org/problem/show?pid=2312 标签是数学，个人感觉很乱搞是很像的； 刚看到这一道题目的时候，一脸懵逼，感觉就是不可做； 后来看题解也看来好长时间； 对于一个函数f(x) 如果f(x)==0,那么0%y一定为0，y是任意数； 所以我们对f(x)取模，多取几次，判断是不是0就好了； 那么取模的数题解说5个差不多，这与为什么我并不知道； 然后多取质数，至于为什么，我也不知道； 为什么一定要取质数啊； 对于 f(x) mod p = f(x%p) mod p 这个其实自己化开来，发现就是多乘几个p，直接%掉的；
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #define Ll long long using namespace std; int a[6][105]; bool ans[6][20000]; int mod[6]={0,11261,19997,22877,21893,14843}; int n,m,sum; char c[10005]; bool ok(int k){ for(int i=1;i<=5;i++) if(!ans[i][k%mod[i]])return 0; return 1; } int main() { scanf("%d%d",&n,&m); n++; for(int i=1;i<=n;i++){ scanf("%s",c+1); int l=strlen(c+1); bool kk=0; if(c[1]=='-')kk=1;else a[1][i]=c[1]-48; for(int j=2;j<=5;j++)a[j][i]=a[j-1][i]; for(int j=1;j<=5;j++){ for(int k=2;k<=l;k++)a[j][i]=(a[j][i]*10+c[k]-48)%mod[j]; if(kk)a[j][i]=-a[j][i]; } } for(int i=1;i<=5;i++){ for(int j=1;j<mod[i];j++){ Ll sum=0,temp=1; for(int k=1;k<=n;k++){ sum=(sum+temp*a[i][k])%mod[i]; temp=temp*j%mod[i]; } if(sum==0)ans[i][j]=1; } ans[i][0]=1; } for(int i=1;i<=m;i++)if(ok(i))sum++; printf("%d\n",sum); for(int i=1;i<=m;i++)if(ok(i))printf("%d\n",i); }