codevs 3732 解方程

时间：2021-09-30 23:24:52

神题不可言会。

f(x+p)=f(x)(mod p)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxl 10050

#define maxn 105

using namespace std;

int n,m,num[maxn][maxl],prime[]={,,,,,},a[maxn],flag[maxn],ans[maxl*],cnt=;

char s[maxl];

bool vis[][];

void solve(int x)

{

    for (int i=;i<=n;i++)

    {

        int data=;

        for (int j=;j<=num[i][];j++)

            data=(data*+num[i][j])%prime[x];

        a[i]=data;

        if (flag[i]) a[i]=-a[i];

    }

    vis[x][]=true;

    for (int i=;i<=prime[x]-;i++)

    {

        int data=a[n]*i%prime[x];

        for (int j=n-;j>=;j--)

            data=(data+a[j])*i%prime[x];

        if (data==) vis[x][i]=true;

    }

}

int main()

{

    memset(flag,false,sizeof(flag));

    scanf("%d%d",&n,&m);

    for (int i=;i<=n;i++)

    {

        scanf("%s",s);

        if (s[]=='-')

        {

            flag[i]=true;

            int len=strlen(s);num[i][]=len-;

            for (int j=;j<=len-;j++)

                num[i][j]=s[j]-'';

        }

        else

        {

            int len=strlen(s);num[i][]=len;

            for (int j=;j<=len-;j++)

                num[i][j+]=s[j]-'';

        }

    }

    for (int i=;i<=;i++)

        solve(i);

    for (int i=;i<=m;i++)

    {

        bool now=true;

        for (int j=;j<=;j++)

            now&=vis[j][i%prime[j]];

        if (now) ans[++cnt]=i;

    }

    printf("%d\n",cnt);

    for (int i=;i<=cnt;i++)

        printf("%d\n",ans[i]);

    return ;

}

相关文章