解方程

2019-04-14 19:29发布

站内文章 / 模拟电子
9637 0 1563
0%任何数都是零
可以用模的周期性，f(x)%k是零，f(x+k)%k也是零，很显然，那么你就模三个质数，像哈希一样
然后推出之后的数，o（m）*3的复杂度，竟会超时 #include #include #include using namespace std; #define ll long long const int M=11000; int n,m;ll f[100000][5]; const int p[]={10007,10917,30071}; ll a[5][110],b[1110],s[1100000],x[]={1,1,1},tot; bool calc(int value, int j) { long long tmp=0; for(int i=n;i>=0;--i) tmp=(tmp*value+a[j][i])%p[j]; return tmp!=0; } int main(){ //freopen("equation.in","r",stdin); //freopen("equation.out","w",stdout); scanf("%d%d ",&n,&m); for(int i=0;i<=n;i++){ char w[M]; gets(w); for(int j=0;j<strlen(w);j++) if(w[j]!='-'){ for(int k=0;k<3;k++) a[k][i]=(a[k][i]*10+w[j]-'0')%p[k]; } for(int k=0;k<3;k++) if(w[0]=='-')a[k][i]=p[k]-a[k][i]; } for(int j=0;j<3;++j) for(int i=0;ifor(int i=1;i<=m;i++){ ll ans=0; int jhfd=0; for(int k=0;k<3;k++) if(f[i%p[k]][k]){ jhfd=1; } if(!jhfd) s[++tot]=i; } printf("%d ",tot); for(int i=1;i<=tot;i++) printf("%lld ",s[i]); }

热门文章