数论鬼题(虽然不算特别数论)
希望你在浏览这篇题解前已经知道了费马小定理
利用用费马小定理构造函数\(g(x)=(x-i)^{P-1}\)
\[x=i,g(x)=0\]
\[x\ne i ,g(x)=1\]
则我们可以构造
\[f(x)=\sum^{i=0}_{P-1}(-a_i*(x-i)^{P-1}+a_i)\]
对于第\(i\)条式子当且仅当\(a_i=1 \ and \ x=i\)时取到\(1\)
代码写的比较奇怪
const int N=3100; int P,a[N]; int po[N]={1},Inv[N]={1,1}; int b[N]; int C(int n,int m){ if(n<0||m<0||n<m) return 0; return po[n]*Inv[m]%P*Inv[n-m]%P; } int fl=0; int main(){ P=rd(); rep(i,1,P+1) po[i]=po[i-1]*i%P; rep(i,2,P-1) Inv[i]=(P-P/i)*Inv[P%i]%P; rep(i,2,P+1) Inv[i]=Inv[i]*Inv[i-1]%P; rep(i,0,P-1) { if(rd()) { fl=1; int t=1; drep(j,P-1,0) b[j]+=C(P-1,j)%P*t%P,t=t*(P-i)%P; } else b[0]++; } rep(i,0,P-1) { int x=(P-b[i])%P; x=(x%P+P)%P; printf("%d%c",x,(i==P-1)?'\n':' '); } }转载于:https://www.cnblogs.com/chasedeath/p/11333881.html
