首页 > 代码库 > 【hash】BZOJ3751-[NOIP2014]解方程

【hash】BZOJ3751-[NOIP2014]解方程

2024-08-16 13:45:17   221人阅读

【题目大意】

 已知多项式方程：a0+a1*x+a2*x^2+...+an*x^n=0。求这个方程在[1,m]内的整数解（n和m均为正整数）。

【思路】

*当年考场上怒打300+行高精度，然而没骗到多少orz 然而正解只有60+行

[前铺]f(n) mod p=f(n mod p) mod p

取四个素数，分别对每个ai取模。先预处理x=0..p-1的情况，直接代入多项式计算即可。再在O(m)时间内检验1..m，对于≥p的利用前铺公式可得。如果模四个素数结果均能得到0，说明这个数是方程的解。

P.S.这个的前提是你的脸好……我一开始随便取的四个就WA了QAQ

 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int MAXN=100+5; 4 const int MAXM=1000000+5; 5 const int MAXP=30000;  6 typedef long long ll; 7 int prime[4]={17389,22349,22367,22369}; 8 int n,m,a[MAXN],hash[MAXN][4],table[MAXP][4],ans[MAXM],cnt=0; 9 10 ll get_table(int j,int x)11 {12     ll ret=0;13     for (int i=n;i>=0;i--)14         ret=(ret*x+hash[i][j])%prime[j];15     return ret;16 }17 18 int read(int x)19 {20     char str[10010];21     scanf("%s",str);22     int negative=0;23     for (int i=0;str[i];i++)24     {25         if (str[i]==‘-‘) negative=1;26             else for (int j=0;j<4;j++)27                     hash[x][j]=((hash[x][j]*10)%prime[j]+(str[i]-‘0‘))%prime[j];28     }29     if (negative)30         for (int j=0;j<4;j++)31             hash[x][j]=(prime[j]-hash[x][j])%prime[j];32 }33 34 void init()35 {36     memset(hash,0,sizeof(hash));37     scanf("%d%d",&n,&m);38     for (int i=0;i<=n;i++) read(i);39     for (int i=0;i<4;i++)40         for (int j=0;j<prime[i];j++) table[j][i]=get_table(i,j);41 }42 43 void solve()44 {45     for (int i=1;i<=m;i++)46     {47         int flag=1;48         for (int j=0;j<4;j++)49             if (table[i%prime[j]][j])50             {51                 flag=0;52                 break;53             }54         if (flag) ans[++cnt]=i;55     }56     printf("%d\n",cnt);57     for (int i=1;i<=cnt;i++) printf("%d\n",ans[i]);58 }59 60 int main()61 {62     init();63     solve();64     return 0;    65 }

 

【hash】BZOJ3751-[NOIP2014]解方程


联系
我们