題目

Description

Input

Output

Sample Input
樣例輸入 1：
2
7
-7
14
樣例輸入 2：
3
1
4
1
5
樣例輸入 3：
0
998244353

Sample Output
樣例輸出 1：
2
7
樣例輸出 2：

樣例輸出 3：
998244353

Data Constraint

更新：N<10^5

Hint
更新：N<10^5

思路

充分性：考慮p|f(x)，即f(x)=kp，即在modp意義下，f(x)=0，根據歐拉定理，分兩種情況討論
x<p，又因為p是質數，那么顯然有(x,p)=1，那么xp?1≡1(modp)，有xp?x≡0(modp)
x≥p，如果gcd(x,p)不為1，那么顯然有gcd(x,p)=p，那么已經滿足p|f(x)，否則套用歐拉定理
必要性：如果p|f(x)，那么0,1,?,p?1必然為f(x)的一個根，那么f(x)有因式x(x?1)(x?2)?(x?(p?1))。我們考慮這個因式與xp?x是等價的，如果不是等價的，那么作差之后，最高次變為p?1，而根的個數卻有p個,顯然矛盾

代碼

#pragma GCC optimize(3) #include<cstdio> #include<cmath> #define ll long long using namespace std; const int N=1e5+77; ll n,a[N],mx,b[100077],cnt,c[N]; ll f[N]; inline void init() {for (int i=2; i<=mx; i++){if(!f[i]) b[++cnt]=i;for (int j=1; j<=cnt && (j==1 || i%(b[j-1])) && b[j]*i<=mx; j++)f[b[j]*i]=-1;}ll s=0;for(int i=1; i<=cnt; i++) s+=b[i]; } signed main() {freopen("poly.in","r",stdin); freopen("poly.out","w",stdout);scanf("%lld",&n);for(register int i=n; i>=0; i--) scanf("%lld",&a[i]);mx=n+1;init();for(register int x=1; x<=cnt; x++){bool bz=1;for(int i=0; i<=n; i++) c[i]=a[i];for(register int i=n; i>=b[x]; i--) c[i-b[x]+1]+=c[i],c[i]=0;for(register int i=0; i<=n; i++) if(c[i]%b[x]!=0){bz=0; break;}if(bz) printf("%lld\n",b[x]);}cnt=0;int t=abs(a[n]),tt=sqrt(t);for(register int i=2; i<=tt; i++){if(t%i==0){while(t%i==0) t/=i;if(i>mx)b[++cnt]=i;}}if(t>mx) b[++cnt]=t;for(register int i=1; i<=cnt; i++){bool bz=1;for(register int j=0; j<n; j++) if(a[j]%b[i]!=0){bz=0; break;}if(bz) printf("%lld\n",b[i]);} }

總結

以上是生活随笔為你收集整理的【JZOJ 省选模拟】多项式（poly）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。