Noip 2014 senior Day2 解方程（equation）

【问题描述】

已知多项式方程：

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

【输入】

输入文件名为 equation.in。

输入共 n+2 行。

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

接下来的 n+1 行，每行包含一个整数，依次为。

【输出】

输出文件名为 equation.out。

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

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

【输入输出样例 1】

equation.in equation.out

2 10 1

1 1

-2

【输入输出样例 2】

2 10 1

2 2

-3 1

【输入输出样例 3】

2 10 0

这道题的话，用同余来想一下就好了。如果原方程成立，那么方程两边同时modp，方程依然成立（显然）。若f(x) ≡0(mod p)则f(x+p) ≡ 0(mod p)。这些都应该是比较好想的对吧。所以我可想到这样来解决：选几个大质数,首先预处理出1-(P-1)代入方程在模P意义下的结果。然后我们枚举解。每次用这几个大质数检验一下即可。

这样一来是不是思路就清晰了。

比较需要注意的是对于高精度的使用，可以选择使用李兄一贯的写在struct里面（但是上次我写错了），也可以就选则使用数组来保存。对于每一个读入的我们首先对它modp然后再存入数组。代入求解什么的就不需要再说了吧。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define N 10010
  6 #define M 1000010
  7 using namespace std;
  8 
  9 const int pri[10] = {11261,23333,10007,21893,14843};
 10 
 11 inline long long read(){ 
 12     long long data=0,w=1; 
 13     char ch=0; 
 14     while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); 
 15     if(ch=='-') w=-1,ch=getchar(); 
 16     while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar(); 
 17     return data*w;
 18 }
 19 
 20 inline void write(long long x)
 21 {
 22      if(x<0) putchar('-'),x=-x;
 23      if(x>9) write(x/10);
 24      putchar(x%10+'0');
 25 }
 26 
 27 int n,m;
 28 int lenth;
 29 int ans[M],a[10][N],aider[10][N],wo[10][N * 5];
 30 char str[N];
 31 
 32 inline int work(int x)
 33 {
 34     int temporary = 0;
 35     for(int i=0;i<=n;i++)
 36     {
 37 //        temporary += a[x][i] * aider[x][i];
 38 //        temporary %= pri[x];
 39         (temporary += a[x][i] * aider[x][i]) %= pri[x];
 40     }
 41     if(temporary < 0) temporary += pri[x];
 42     return temporary;
 43 }
 44 
 45 inline bool check(int x)
 46 {
 47     for(int i=0;i<=4;i++) if(wo[i][x%pri[i]] != 0) return false;
 48     return true;
 49 }
 50 
 51 int main()
 52 {
 53     freopen("equation.in","r",stdin);
 54     freopen("equation.out","w",stdout);
 55     
 56     n = read();
 57     m = read();
 58     for(int i=0;i<=n;i++)
 59     {
 60         scanf("%s",str+1);
 61         bool flag = true;
 62         lenth = strlen(str+1);
 63         for(int j=0;j<=4;j++) // 该数 mod p[j]下的结果 
 64         {
 65             if (str[1] != '-') a[j][i] = str[1] - '0';
 66             else flag = false;
 67             for(int k=2;k<=lenth; k++)
 68             {
 69 //                a[j][i] = a[j][i] * 10 + str[k];
 70 //                a[j][i] %= pri[j];
 71                 (a[j][i] = a[j][i] * 10 + str[k] - '0') %= pri[j];
 72             }
 73             if(!flag) a[j][i] = -a[j][i];
 74         }
 75     }
 76     for(int i=0;i<=4;i++)
 77     {
 78         for(int j=1;j<=pri[i]-1;j++) // 预处理大素数之前的所有数代入方程后 mod pri[i]的结果 
 79         {
 80              aider[i][0] = 1;
 81              for(int k=1;k<=n;k++)
 82              {
 83 //                 aider[i][k] = aider[i][k-1] * j;
 84 //                 aider[i][k] %= pri[i];
 85                  (aider[i][k] = aider[i][k-1] * j) %= pri[i];
 86              }
 87              wo[i][j] = work(i);
 88         }
 89     }
 90     for(int i=1;i<=m;i++)
 91     {
 92         if(check(i)) ans[++ans[0]] = i;
 93     }
 94     write(ans[0]);
 95     putchar('
');
 96     for(int i=1;i<=ans[0];i++)
 97     {
 98         write(ans[i]);
 99         putchar('
');
100     }
101     
102     return 0;
103 }
104 /*
105 若f(x) ≡0(mod p)则f(x+p) ≡0(mod p);
106 若原方程成立。那么在方程两边同时模P,方程仍然成立。
107 所以我们可以选几个大质数,首先预处理出1-(P-1)代入方程在模P意义下的结果。
108 然后我们枚举解。每次用这几个大质数检验一下即可。
109 */