bzoj 3751: [NOIP2014]解方程【数学】

……我真是太非了，自己搞了7个质数都WA，从别人那粘5个质数就A了……

就是直接枚举解，用裴蜀定理计算是否符合要求，因为这里显然结果很大，所以我们对多个质数取模看最后是不是都为0

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1000005,p[]={11261,19997,22877,21893,14843};

long long n,m,a[110][10],cnt[N];

bool f[N][10];

char s[N];

bool clc(int v,int j)

{

    long long r=0;

    for(int i=n;i>=0;--i)

		r=(r*v+a[i][j])%p[j];

    return r!=0;

}

int main()

{

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

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

    {

        scanf("%s",s);

        int len=strlen(s),fl=1;

        for(int l=0;l<len;++l)

        {

            if(s[l]=='-')

				fl=-1;

            else

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

					a[i][j]=(a[i][j]*10+s[l]-'0')%p[j];

        }

        if(fl==-1)

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

				a[i][j]=p[j]-a[i][j];

    }

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

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

			f[i][j]=clc(i,j);

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

    {

        bool fl=1;

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

			if(f[i%p[j]][j])

			{

				fl=0;

				break;

			}

        if(fl)

			cnt[++cnt[0]]=i;

    }

    printf("%d\n",cnt[0]);

    for(int i=1;i<=cnt[0];++i)

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

    return 0;

}

巴特西

bzoj 3751: [NOIP2014]解方程【数学】

最新文章

热门文章