[BZOJ3751] [NOIP2014] 解方程 (数学)

2023-12-19 19:51:51

Description

　　已知多项式方程：$a_0+a_1*x+a_2*x^2+...+a_n*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

Sample Output

2
1
2

HINT

　　对于100%的数据，0<n≤100，|ai|≤10^10000，an≠0，m≤1000000。

Source

Solution

　　考虑对等式左边整体对质数取模，这部分用秦九韶算法实现可以大大提速，并且可以避免大量的高精度运算

　　假设模数为$p$，不难发现在模$p$意义下$x$与$x+kp$得到的结果一样，所以我们可以预处理出$[0,p)$的答案，推出$[1,m]$是否可能是解

　　因为$p$很小会有类似哈希冲撞的事发生，所以我们可以选取多个$p$。据说是选$5$个$20000$左右的质数就可以，然而我换过好几个质数，不是$WA$就是$TLE$，QAQ

　　代码里的质数是网上找的，并不清楚为什么这人的人品能那么好QAQ，$4$个质数就可以$AC$QAQ

　　（方法会就行了，这道题考的不是质数的选取，质数照抄就行了）

 #include <bits/stdc++.h>

 using namespace std;

 char s[][];

 int p[] = {, , , };

 int n, a[], ans[];

 bool vis[][];

 bool check(int x)

 {

     if(!vis[][x % ]) return false;

     if(!vis[][x % ]) return false;

     if(!vis[][x % ]) return false;

     if(!vis[][x % ]) return false;

     return true;

 }

 bool is_zero(int k, int x)

 {

     long long ans = a[n];

     for(int i = n - ; ~i; --i)

         ans = (ans * x + a[i]) % p[k];

     return !ans;

 }

 int main()

 {

     int m, tot = ;

     scanf("%d%d", &n, &m);

     for(int i = ; i <= n; ++i)

         scanf("%s", &s[i]);

     for(int i = ; i < ; ++i)

     {

         memset(a, , sizeof(a));

         for(int j = ; j <= n; ++j)

             if(s[j][] == '-')

                 for(int k = ; s[j][k]; ++k)

                     a[j] = (a[j] *  - s[j][k] +  + p[i]) % p[i];

             else

                 for(int k = ; s[j][k]; ++k)

                     a[j] = (a[j] *  + s[j][k] - ) % p[i];

         for(int j = ; j < p[i]; ++j)

             vis[i][j] = is_zero(i, j);

     }

     for(int i = ; i <= m; ++i)

         if(check(i)) ans[++tot] = i;

     printf("%d\n", tot);

     for(int i = ; i <= tot; ++i)

         printf("%d\n", ans[i]);

     return ;

 }

码农公寓