首页 > 代码库 > [BZOJ 3751][NOIP2014]解方程（哈希）

[BZOJ 3751][NOIP2014]解方程（哈希）

2024-09-19 00:34:30   215人阅读

Description

已知多项式方程：

a0+a1*x+a2*x^2+...+an*x^n=0

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

Solution

一道很久很久以前就应该做的noip的题

一定要放上来是要见证我人品崩坏的一下午

生无可恋…QAQ

题解其实也很简单啦

随便找几个素数取模验证是不是等于0就好了

随便

随便

随便

随便找几个…素数

在WA\TLE\OLE间切换，最后还是抄了别人的几个素数

怀疑人生【望天

（BZOJ上的数据是加强了的，如果是ccf的数据那当然就随便找几个素数啦…）

加23333保平安

技术分享

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>using namespace std;typedef long long LL;int prime[5]={839,233,23333,22877,19997},a[105][5];int n,m,cnt=0,t[1000005];char s[10005];int judge[1000005];int read(char* s,int p){    int x=0,f=1,i=0;    while(s[i]<‘0‘||s[i]>‘9‘){if(s[i]==‘-‘)f=-1;i++;}    while(s[i]>=‘0‘&&s[i]<=‘9‘)x=(x*10+s[i]-‘0‘)%p,i++;    return x*f;}int main(){    scanf("%d%d",&n,&m);    for(int i=0;i<=n;i++)    {        scanf("%s",s);        for(int j=0;j<5;j++)        a[i][j]=read(s,prime[j]);    }    for(int i=0;i<5;i++)    {        for(int j=0;j<prime[i]&&j<=m;j++)        {            int pow=1;LL ans=0;            for(int k=0;k<=n;k++)            {                ans+=(1LL*pow*a[k][i])%prime[i];                ans%=prime[i];                pow=(1LL*pow*j)%prime[i];            }            if(!ans)            {                for(int k=0;k*prime[i]+j<=m;k++)                judge[k*prime[i]+j]++;            }        }    }    for(int i=1;i<=m;i++)    if(judge[i]==5)t[++cnt]=i;    printf("%d\n",cnt);    for(int i=1;i<=cnt;i++)    printf("%d\n",t[i]);    return 0;}

 

[BZOJ 3751][NOIP2014]解方程（哈希）


联系
我们