解方程

题目描述

已知多项式方程：

a0+a1x+a2x^2+..+anx^n=0

求这个方程在[1, m ] 内的整数解（n 和m 均为正整数）

输入输出格式

输入格式：

输入文件名为equation .in。

输入共n + 2 行。

第一行包含2 个整数n 、m ，每两个整数之间用一个空格隔开。

接下来的n+1 行每行包含一个整数，依次为a0,a1,a2..an

输出格式：

输出文件名为equation .out 。

第一行输出方程在[1, m ] 内的整数解的个数。

接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m ] 内的一个整数解。

输入输出样例

输入样例#1：

输出样例#1：

1
1

输入样例#2：

输出样例#2：

2
1
2

输入样例#3：

输出样例#3：

说明

30%:0<n<=2,|ai|<=100,an!=0,m<100

50%:0<n<=100,|ai|<=10^100,an!=0,m<100

70%:0<n<=100,|ai|<=10^10000,an!=0,m<10000

100%:0<n<=100,|ai|<=10^10000,an!=0,m<1000000

题解：

本题不需要高精度。

只需要在计算时取膜便可。

0 mod任何数都等于0，而要使x为方程的解，则必有左边=0，即f(x)=0

那么此时显然f(x) mod p=0 mod p=0，p为某质数(3个左右，4个超时)

但当f(x)==k*p>0则不成立，所以多膜几个，同时成立的概率几乎为0

首先读入a时就要取膜，膜后为a'，并用3个数组存3组a',对应3个f(x)；

从1~m带入三个f(x)中，用秦九韶算法就可以边算边膜

友情提供3组质数：12347,1007,1727191

注：此代码可过正常数据，但无法通过bzoj上的加强数据，如想在bzoj上通过，请老老实实写高精度

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 int mod[4]={0,12347,1007,1727191};
 7 int s[100001];
 8 bool vis[1005001];
 9 long long f[101][4],m,n,ans;
10 bool pd(int j,long long x)
11 {long long i;
12     long long y=0;
13     for (i=n;i>=1;i--)
14      {
15          y=(y+f[i][j])%mod[j];
16          y=y*x%mod[j];
17      }
18     y=(y+f[0][j])%mod[j];
19     if (y==0) return 1;
20     else return 0;
21 }
22 int main()
23 {char ch;
24 long long i;
25     cin>>n>>m;
26     ch=getchar();
27     for (i=0;i<=n;i++)
28     {int ff=0,len=0;
29         ch=getchar();
30         while (ch=='-'||(ch>='0'&&ch<='9'))
31         {
32             if (ch=='-') ff=1;
33             else 
34             {
35                 len++;
36                 s[len]=ch-'0';
37             }
38             ch=getchar();
39         }
40          for (int j=1;j<=3;j++)
41           {
42               int x=0;
43               for (int l=1;l<=len;l++)
44                {
45                    x=(x*10+s[l])%mod[j];
46                }
47                f[i][j]=x;
48                if (ff) f[i][j]*=-1;
49           }
50     }
51      for (i=1;i<=m;i++)
52      if (vis[i]==0)
53      {
54          for (int j=1;j<=3;j++)
55          if (!pd(j,i)) 
56          {
57            long long k=i;
58            while (k<=m)
59            {
60                vis[k]=1;
61                k+=mod[j];
62            } 
63          }
64      }
65     for (i=1;i<=m;i++)
66     if (vis[i]==0)
67     {
68         ans++;
69     }
70     cout<<ans<<endl;;
71     for (i=1;i<=m;i++)
72     if (vis[i]==0)
73     {
74         printf("%lld
",i);
75     }
76 }