noip 2014 Day2 T3 解方程

    UOJ解方程

题意

    求方程a0+a1∗x+a2∗x2+a3∗x3+......an∗xn=0在[1,m]内的整数解。|ai|<=1010000,n<=100,m<=1000000

I think

    对于f(x)=a0+a1∗x+a2∗x2+a3∗x3+......an∗xn=0,若f(x) = 0, 则f(x)%p = 0. 反之则不一定，但是若多取几个质数p，正确的几率就比较大。于是取若干p，若x对于任意p均满足f(x)%p == 0,则x为可行解。
    若f(x) % p = 0,则f(x+p) = 0. 于是对于质数pi仅判断小于pi的数x是否为可行解，等价于判断模pi等于x的所有数是否为可行解。
    ai范围较大，而加法与乘法是不影响取模的，于是用字符串输入ai,将其转化为10进制数时边转边模。

Code

#include #include #include using namespace std; const int sm = 100 + 5; const int sn = 1e6 + 5; const int p[6] = {0,9769,8719,8269,7717,7583}; int n,m; char str[10010]; int a[6][sm],pre[sm],ans[sn]; bool ret[6][10010]; bool Calc(int k) { int res = 0; for(int i = 0; i <= n; ++i) res = (res + a[k][i]*pre[i])%p[k]; if(res<0) res+=p[k]; return res; } bool Judge(int x) { for(int k = 1;k <= 5; ++k) if(ret[k][x%p[k]]) return false; return true; } int main() { int len; bool flag; scanf("%d%d",&n,&m); for(int i = 0; i <= n; ++i) { scanf("%s",str+1); len = strlen(str+1); flag = 0; for(int k = 1; k <= 5; ++k) if(str[1] == '-') a[k][i] = 0,flag= 1; else a[k][i] = str[1] - '0'; for(int k = 1; k <= 5; ++k) { for(int j = 2; j <= len; ++j) a[k][i] = (a[k][i]*10 + str[j] -'0')%p[k]; if(flag) a[k][i] *= -1; } } for(int k = 1; k <= 5; ++k) for(int i = 1; i < p[k]; ++i) { pre[0] = 1; for(int j = 1; j <= n; ++j) pre[j] = pre[j-1]*i%p[k]; ret[k][i] = Calc(k); } for(int i = 1; i <= m; ++i) if(Judge(i)) ans[++ans[0]] = i; printf("%d ",ans[0]); for(int i = 1; i <= ans[0]; ++i) printf("%d ",ans[i]); return 0; }