跟付公主的背包很像,可以先做做那一题.
然后也是ln,exp转化,ln求和之后发现不太好做,转化给f序列求ln,使等号两边相等.
问题就转化为了,选出一些数,使对于每一个i,在这些数里面的约数和为i*fi.显然是莫比乌斯反演即可.
#include<bits/stdc++.h> using namespace std; int mod; int ksm(int x,int t){ int tot=1; while(t){ if(t&1) tot=1ll*tot*x%mod; x=1ll*x*x%mod; t/=2; } return tot; } const int N=2000010; int limit,where[N],inv[N]; int n,mu[N],p[N]; bool vis[N]; struct Complex { long double x, y; Complex(long double xx = 0, long double yy = 0): x(xx), y(yy) {} }; inline Complex operator+(const Complex&a,const Complex&b){return Complex(a.x+b.x,a.y+b.y);} inline Complex operator-(const Complex&a,const Complex&b){return Complex(a.x-b.x,a.y-b.y);} inline Complex operator*(const Complex&a,const Complex&b){return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);} inline Complex operator/(const Complex&a,const long double p){return Complex(a.x/p,a.y/p);} inline Complex conj(const Complex&a){return Complex(a.x,-a.y);} const long double Pi=acos(-1.0); Complex I=Complex(0,1); void prepare(int n){ int l=0; limit=1; while(limit<=n) limit<<=1,l++; for(int i=0;i<limit;i++) where[i]=(where[i>>1]>>1)|((i&1)<<(l-1)); } void FFT(Complex*now,int op){ for(int i=0;i<limit;i++) if(i<where[i]) swap(now[i],now[where[i]]); for(int u=0,l=1;l<limit;u++,l<<=1){ Complex wn=Complex(cos(Pi/l),op*sin(Pi/l)); for(int i=0;i<limit;i+=l*2){ Complex w=Complex(1,0); for(int v=0;v<l;v++,w=w*wn){ int x=i+v,y=i+l+v; Complex a=now[x],b=now[y]*w; now[x]=a+b;now[y]=a-b; } } } if(op==-1) for(int i=0;i<limit;i++) now[i]=now[i]/limit; } void DFT(Complex*a,Complex*b){ for(int i=0;i<limit;i++) a[i]=a[i]+b[i]*I; FFT(a,1);b[0]=conj(a[0]); for(int i=1;i<limit;i++) b[i]=conj(a[limit-i]); for(int i=0;i<limit;i++){ Complex t1=a[i],t2=b[i]; a[i]=(t1+t2)/2; b[i]=(t1-t2)*I/(-2); } } void IDFT(Complex*a,Complex*b){ for(int i=0;i<limit;i++) a[i]=a[i]+b[i]*I; FFT(a,-1);for(int i=0;i<limit;i++) b[i].x=a[i].y; } void MUL(int*A,int*B,int n,int m){ prepare(n+m-2); static Complex a[N],b[N],c[N],d[N]; for(int i=n;i<limit;i++) A[i]=0; for(int i=m;i<limit;i++) B[i]=0; for(int i=0;i<limit;i++){ a[i]=Complex(A[i]>>15,0),b[i]=Complex(A[i]&32767,0); c[i]=Complex(B[i]>>15,0),d[i]=Complex(B[i]&32767,0); } DFT(a,b);DFT(c,d); for(int i=0;i<limit;i++){ Complex t1=a[i],t2=b[i],t3=c[i],t4=d[i]; a[i]=t1*t3,b[i]=t1*t4; c[i]=t2*t3,d[i]=t2*t4; } IDFT(a,b);IDFT(c,d); for(int i=0;i<limit;i++) A[i]=((((long long)(a[i].x+0.5)%mod)<<30)%mod +(((long long)(b[i].x+0.5)%mod+(long long)(c[i].x+0.5)%mod)<<15)%mod +(long long)(d[i].x+0.5)%mod)%mod; } void INV(int*f,int n){ if(n==1){f[0]=ksm(f[0],mod-2);return ;} int f0[n<<2]; for(int i=0;i<(n+1)/2;i++) f0[i]=f[i]; INV(f0,(n+1)/2); int g[n<<2]; for(int i=0;i<(n+1)/2;i++) g[i]=f0[i]*2,g[i]>=mod?g[i]-=mod:0; MUL(f0,f0,(n+1)/2,(n+1)/2); MUL(f,f0,n,(n+1)/2+(n+1)/2-1); for(int i=0;i<(n+1)/2;i++) f[i]=g[i]+mod-f[i],f[i]>=mod?f[i]-=mod:0; for(int i=(n+1)/2;i<n;i++) f[i]!=0?f[i]=mod-f[i]:0; } void DAO(int*f,int n){for(int i=0;i<n-1;i++) f[i]=1ll*f[i+1]*(i+1)%mod;f[n-1]=0;} void JI(int*f,int n){for(int i=n;i>=1;i--) f[i]=1ll*f[i-1]*inv[i]%mod;f[0]=0;} void LN(int*f,int n){ static int g[N]; for(int i=0;i<n;i++) g[i]=f[i]; DAO(g,n);INV(f,n);MUL(f,g,n,n-1);JI(f,n-1); } int a[N],b[N]; int main(){ scanf("%d %d",&n,&mod); inv[1]=1;for(int i=2;i<=n;i++) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod; for(int i=1;i<=n;i++) scanf("%d",&a[i]);a[0]=1; LN(a,n+1);mu[1]=1; for(int i=2;i<=n;i++) { if(!vis[i]) mu[i]=mod-1,p[++p[0]]=i; for(int j=1;j<=p[0] && 1ll*i*p[j]<=n;j++){ vis[i*p[j]]=true; if(i%p[j]==0) break; if(mu[i]) mu[i*p[j]]=(mu[i]==1?mod-1:1); } } for(int i=1;i<=n;i++) a[i]=1ll*a[i]*i%mod; int m=0; for(int i=1;i<=n;i++){ for(int j=1;i*j<=n;j++) (b[i*j]+=1ll*mu[i]*a[j]%mod)%=mod; m+=(b[i]==i); } printf("%d\n",m); for(int i=1;i<=n;i++) if(b[i]==i) printf("%d ",i); }
