当前位置: 代码迷 >> 综合 >> luogu P2312 解方程
  详细解决方案

luogu P2312 解方程

热度:72   发布时间:2024-02-25 16:24:37.0

题面传送门
数据太大了,所以要hash。
多取几个模数正确性更高。
代码实现:

#include<cstdio>
#define mod 1000000007
using namespace std;
int x,y,z,n,m,k,head,ans[100039],fff;
long long tot,a[100039],now;
char _s;
int main(){
    
// freopen("1.in","r",stdin);register int i,j;scanf("%d%d",&n,&m);for(i=0;i<=n;i++) {
    _s=getchar();fff=1;while(_s<'0'||_s>'9') {
    if(_s=='-') fff=-1;_s=getchar();}while(_s>='0'&&_s<='9') a[i]=(a[i]*10+_s-48)%mod,_s=getchar();a[i]*=fff;a[i]=(a[i]+mod)%mod;}for(i=1;i<=m;i++){
    now=a[n];for(j=n-1;j>=0;j--) now=(now*i+a[j])%mod;if(!now){
    ans[++head]=i;} }printf("%d\n",head);for(i=1;i<=head;i++) printf("%d\n",ans[i]);
}