【题解】洛谷P2312[NOIP2014]解方程 枚举+数学知识

题目链接

枚举答案x，计算上面那个式子的值，可以选择边算边模（某个八位质数），免得打高精，一般不会死。

#include<cstdio>
#include<vector>
using namespace std;
const int mod=19260817,M=1e6+10;
typedef long long ll;
template<typename tp>inline void read(tp &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=((x<<1)%mod+(x<<3)%mod+(ch^48))%mod,ch=getchar();
	if(f)x=-x;
}
template<typename tp>inline void write(tp x)
{
	int buf[40],p=0;
	if(x<0)putchar('-'),x=-x;
	do{
		buf[p++]=x%10;x/=10;
	}while(x);
	for(int i=p-1;i+1;i--)putchar(buf[i]+48);
	putchar('\n');
}
ll n,m,a[110];
bool check(int x)
{
	int sum=0;
	for(int i=n;i;i--)
	    sum=(sum+a[i])*x%mod;
	sum=(sum+a[0]+mod)%mod;
	return !sum;
}
vector<int>v;
int main()
{
	//freopen("in.txt","r",stdin);
	read(n);read(m);
	for(int i=0;i<=n;i++)
	    read(a[i]);
	int flag=0,cnt=0;
	for(int i=1;i<=m;i++)
	    if(check(i)){cnt++;flag=1;v.push_back(i);}
	if(!flag)puts("0");
	else 
	{
		write(cnt);
		for(vector<int>::iterator it=v.begin();it!=v.end();it++)
		    write(*it);
	}
	return 0;
}

总结

通过模质数减小了题目难度。