题面
解方程和解比例计算题?
解析
这题的数据看起来似乎特别吓人。。。
但实际上,
这题非常好想。
只需要模一个大质数就行了(我模的是1e9+7)(实测有效)
另外,a要用快读读入,再一边模Mod(因为实在太大了)。
然后,秦九韶算法了解一下:
秦九韶算法
接下来,只需要枚举1~m的所有整数再判断就行了。
然而,这一切并没有结束...
这样的时间复杂度是O(n*m)
所以稍微有点常数就会被卡(惨痛的经验教训),
因此,我们要直接开long long,在最后模一下Mod就行了(不然会被卡)。
上AC代码:
#include <bits/stdc++.h> #define ll long long using namespace std;const int Mod1=1e9+7,Mod2=1e9+9; ll n,m,a1[1001],a2[1001]; ll ans[100001];bool isroot(int x){ll ret1=0,ret2=0;for(int i=n;i;i--){ret1=((ret1+a1[i])*x)%Mod1;}ret1=(ret1+a1[0])%Mod1;return !ret1; }void read1(int k){ll x1=0,x2=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){x1=(ll)(x1*10+(ch-'0'))%Mod1;ch=getchar();}a1[k]=x1*f; } void print(int x){if(x<0) putchar('-'),x=-x;if(x>9) print(x/10);putchar(x%10+'0'); }int main(){scanf("%lld%lld",&n,&m);for(int i=0;i<=n;i++){read1(i);}for(int i=1;i<=m;i++){if(isroot(i)) ans[++ans[0]]=i;}print(ans[0]);printf("\n");for(int i=1;i<=ans[0];i++){print(ans[i]);printf("\n");}return 0; }