题解
本题重点考察数学知识,可分成以下三点:秦九韶算法、取模运算律,long long等数据类型的细节。
秦九韶算法:
假设有一元4次方程a0+a1*x+a2*x2+a3x3+a4x4=0,那么其等于 (x(x(xa4+a3)+a2)+a1)+a0=0。在此题中同理,最后算出答案判断是否为0。
取模运算律:
数据类型:
在此题中a的数据范围极大,在读入、计算和判定其最终是否为0的过程中可以模大~质数防爆int,且不会影响结果。在读入时使用读入优化,边读入边取模。
最后附代码~有详细注释
#include<stdio.h> #include<algorithm> using namespace std; const int mod=1000000007; int a[105],b[1000005]; long long int read()//d读入优化 { long long int sign=1,data=0; char c; c=getchar(); while(c>'9'||c<'0') { if(c=='-')sign=-1;//读到负号记录 c=getchar(); } while(c<='9'&&c>='0') { data=(data*10+(c-'0'))%mod;//a可能很大所以在读入时取模 c=getchar(); } return data*sign;//如果是负数sign==-1,那么返回的值为负数 } int main() { int n,m,num=0; int ans;//ans记录多项式的结果 scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) a[i]=read(); for(long long i=1;i<=m;i++) { ans=0; for(long long j=n;j>=1;j--) { ans=(ans+a[j])*i%mod; //这里套用秦九韶算法求多项式的值 注意a[0]并不需要乘x } ans=(ans+a[0])%mod;//这里再加上a[0] if(ans==0) { num++;//记录解的个数 b[num]=i;//记录每个解的值 } } printf("%d\n",num); for(int i=1;i<=num;i++) { printf("%d\n",b[i]); } return 0; }