LOJ2503 NOIP2014 解方程【HASH】

LOJ2503 NOIP2014 解方程

LINK

题目大意就是给你一个方程，让你求中的解，其中系数非常大

看到是提高T3还是解方程就以为是神仙数学题

后来研究了一下高精之类的算法发现过不了多少分

后面佬说这题是hash

然后就雾

考虑对于一个式子肯定会满足
所以我们直接多取几个相近的prime，减小冲突几率

然后我们只需要预处理每个系数对于每个prime的模数，然后判断一下就可以了

但是这样会TLE

又可以发现对于任意的，等价于
所以对于每个质数直接枚举比它小的数进行检查就好了

然后就比较和谐了

中间出了一些比较玄学的错误导致交了很多个70分
不过问题不大

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 110
 4 #define M 1000010
 5 int prime[5]={10099,10103,10111,10133,10139};
 6 int pa[N][5],n,m;
 7 char c[M];
 8 bool vis[M],ak[M][5];
 9 int check(int x,int id){
10   int pic=0;
11   for(int i=n;i>=0;i--)
12     pic=(pic*x%prime[id]+pa[i][id])%prime[id];
13   return pic;
14 }
15 int main(){
16   scanf("%d%d",&n,&m);
17   for(int i=0;i<=n;i++){
18     scanf("%s",c);
19     int len=strlen(c),j=0;
20     if(c[0]=='-')j++;
21     for(;j<len;j++)for(int k=0;k<5;k++)
22       pa[i][k]=(pa[i][k]*10+c[j]-'0')%prime[k];
23       if(c[0]=='-')for(int k=0;k<5;k++)pa[i][k]*=-1;
24     }
25     int cnt=0;
26     for(int j=0;j<5;j++)
27       for(int i=0;i<prime[j];i++)
28         if(check(i,j)!=0)ak[i][j]=1;
29     for(int i=1;i<=m;i++){
30       bool can=1;
31       for(int j=0;j<5;j++)if(ak[i%prime[j]][j]){can=0;break;}
32     if(can)vis[i]=1,cnt++;
33   }
34   printf("%d
",cnt);
35   for(int i=1;i<=m;i++)if(vis[i])printf("%d
",i);
36   return 0;
37 }

LOJ2503 NOIP2014 解方程 【HASH】

LOJ2503 NOIP2014 解方程

LOJ2503 NOIP2014 解方程【HASH】