Flandre Scarlet's Blog

Description

Input

Output

--------------------------------0-------------------------------

妈呀这题我不会【滑稽再见】。

-------------------------------30-------------------------------

CCF的30%枚举拿拿还是很开心的【括弧笑】。

-------------------------------50-------------------------------

50%高精模拟？

听说某位线段树大师写挂了2333。

----------------------------思考人生----------------------------

怎么搞呢？

脑子想想都觉得100%高精不靠谱（高精加减乘方复杂度怎么看就愉♂悦）。

把范围缩小？

有没有听过这样一句话：由于XXXX的方案数太多，输出时要对100000007取模。

好熟悉的梗！

于是Get了一个新姿势：

-------------------------------70-------------------------------

选取几个较大素数（例如10000-20000之间的）

对于每个x，算出f(x)%pi，如果f(x)=0则f(x)%pi必然=0，多选几个素数，就可以在一定范围大小内判断成功。

但是不够快QAQ

-------------------------二段思考人生--------------------------

70拿拿也蛮好的，就当总分570做！

不对，这是练习，不是比赛现场。

搜题解：【定理：f(x)≡f(x+p)%p 这里f(x)为整系数多项式】

真TM机智！（二项式定理可以眼秒证明）

------------------------------100-------------------------------

对于一个x，f(x)≠0(mod p)，则x+p,x+2p……均不为方程的解。

筛法大法好！

------------------------------150-------------------------------

m<=10^8

https://vijos.org/p/1915/solution @doc @sujiao

100分脑残Code：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define M 110
#define R 6
#define G getchar()
using namespace std;
int a[10005],A[M],P[R]={30011,11261,14843,19997,10007,21893},N,H[M][R],L,S=0,V,p,X,sum,x,n,m,W;
bool C[1000005];char ch;
int main()
{
	scanf("%d%d\n",&n,&m);
	for (int i=0;i<=n;i++)
	{
		L=0;
		if ((ch=G)=='-') N=-1;
		else a[L++]=ch-48,N=1;
		while ((ch=G)>47)a[L++]=ch-48;
		scanf("\n");
		for (int p=0;p<R;p++)
		{
			W=0;
			for (int w=0;w<L;w++)W=(W*10+a[w])%P[p];
			H[i][p]=(P[p]+W*N)%P[p];
		} 
	}
	for (int i=1;i<=m;i++)
	{
		V=1;
		if (C[i]) continue;
		for (int j=0;j<R;j++)
		{
			p=P[j],x=i%p,sum=0,X=1;
			for (int k=0;k<=n;k++) sum=(sum+X*H[k][j])%p,X=(X*x)%p;	
			if (sum)
			{
				for (int k=i;k<=m;k+=P[j])C[k]=1;
				V=0;break;
			}
		}
		if (V) A[++S]=i;
	}
	printf("%d\n",S);
	for (int i=1;i<=S;i++)
		printf("%d\n",A[i]);
	return 0;
}

150分Code：(由于O(n^3+n*sqrt(m))导致常规数据下比O(m)慢)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxn 110
#define pri 4
using namespace std;
typedef long long LL;
int a[10010],prime[4]={10007,10009,12007,13001},neg,hehe[110][4],l;
int s[110][2],la[2],anss[110],ans;
char ch;
void gcd(LL a,LL b,LL& d,LL& x,LL &y)//ax+by=d
{
	if (!b)d=a,x=1,y=0;
	else gcd(b,a%b,d,y,x),y-=x*(a/b);
}
LL CRT(LL a1,LL p1,LL a2,LL p2)//%a1=p1 %a2=p2
{
	LL s=a2-a1,k1,k2,pp=p1*p2,d;
	gcd(p1,-p2,d,k1,k2);
	s=(s%pp+pp)%pp;
	k1=(k1%pp+pp)%pp;
	//d=1;
	k1=k1*s%pp;
	return (k1*p1%pp+a1%pp)%pp;
}
int main()
{
	int n,m;
	scanf("%d%d\n",&n,&m);
	for (int i=0;i<=n;i++)
	{
		l=0;
		ch=getchar();
		if (ch=='-') neg=-1;
		else {a[l++]=ch-48;neg=1;}
		ch=getchar();
		while (ch<=57&&ch>=48)
		{
			a[l++]=ch-48;
			ch=getchar();
		}
		scanf("\n");
		for (int p=0;p<pri;p++)
		{
			int ans=0;
			for (int w=0;w<l;w++)
				ans=(ans*10+a[w])%prime[p];
			hehe[i][p]=(prime[p]+ans*neg)%prime[p];
		} 
	}
	int ans=0;
	for(int A=0;A<2;A++)
	{
		for (int i=1;i<=prime[A];i++)//枚举答案 
		{
			int p=prime[A],x=i%p,sum=0,X=1;
			for (int k=0;k<=n;k++)//
				sum=(sum+X*hehe[k][A])%p,X=(X*x)%p;	
			if (!sum) {s[++la[A]][A]=i;}
		}
	}
	for(int I=1;I<=la[0];I++)
		for(int J=1;J<=la[1];J++)
		{
			int vic=1,i=CRT(s[I][0],prime[0],s[J][1],prime[1]);
			if(i>m)continue;
			for (int j=0;j<pri;j++)//判素数 
			{
				int p=prime[j],x=i%p,sum=0,X=1;
				for (int k=0;k<=n;k++)//
					sum=(sum+X*hehe[k][j])%p,X=(X*x)%p;	
				if (sum)
				{
					vic=0;
					break;
				}
			}
			if (vic) {anss[++ans]=i;}
		}
	if(!ans)puts("0");
	else
	{
		sort(anss+1,anss+1+ans);
		printf("%d\n",ans);
		for (int i=1;i<=ans;i++)
			printf("%d\n",anss[i]);
	}
	return 0;
}