[NOIP2014] 解方程
思路
首先我们可以观察到 和 与 相比小的很多,所以我们可以考虑直接暴力求解
但是 太大了,所以如果需要直接计算的话需要全程使用高精度算法。
因为高精度算法代码量有大速度又慢我们可依考虑将 转化为一个极大的指数取模的结果,因为只有是模数的倍数或者本身就是 的数取模才会是 。
为了避免出现模数的倍数,可以使用两个模数减小概率(像双哈希一样)但是也可以将模数设置的大一点减小几率。可是两个模数码量过大,我们可以直接使用一个大质数(相信出题人不会卡我们的)。
因为题目给出的式子过于的复杂,其实可以使用秦九韶算法进行化简
虽说名字叫秦九韶算法,但是其实就是将每一项内的因子提取了出来,即使不化简也一样可以做出来。
在简化之后,就可以从最里层的括号开始,逐层向外递推,码量就少了很多。经过递推,很快的就可以得到表示的值了,时间复杂度为 。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,m,a[105];
vector<int> v;
inline int read(){
int x=0,f=1;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') f=-1,ch=getchar();
while(ch<='9'&&ch>='0') x=((x<<1)+(x<<3)+ch-48)%mod,ch=getchar();
return x*f;
}
void solve(int x){
int cnt=a[n];
for(int i=n;i>=1;i--) cnt=(cnt*x%mod+a[i-1]+mod)%mod;
if(cnt==0) v.push_back(x); //储存答案
}
signed main(){
n=read(),m=read();
for(int i=0;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) solve(i);
cout<<v.size()<<endl;
for(int i:v) cout<<i<<endl; //将数组v中的元素依次赋值给变量i
return 0;
}