题解：
首先先弄出$f(x)$的生成函数
$$f(x)=\prod_{i=1}^{n} {{(\frac{1}{1-x^i})}}^{a[i]}$$
因为$f(x)$已知，我们考虑利用这个式子取推出$a[i]$
右边的乘法显然处理起来不方便，按照套路两边取对数
$$ln(f(x))=\sum_{i=1}^{n} {-a[i]*ln(1-x^i)}$$
然后看见$ln(1+x)$肯定是泰勒展开了，得到
$$ln(f(x))=\sum_{i=1}^{n} {-a[i]*\sum_{k=1}^{INF} {\frac{{(-1)}^{k-1}*{{{(-x^i)}^k}}}{k}}}$$
化简一下就是
$$ln(f(x))=\sum_{i=1}^{n} {a[i]*\sum_{k=1}^{INF} {\frac{{x^{ik}}}{k}}}$$
然后因为我们知道的$f(x)$的每一项,所以变成枚举x系数
令$T=ik$
$$ln(f(x))=\sum_{T=1}^{INF} {x^T \sum_{i|T}^{T}{\frac{i*a[i]}{T}}}$$
然后我们只需要从小到大枚举T，然后依旧算出每个$a[i]$并处理对之后的影响
常数太大只有50。。。不知道怎么卡
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define me(x) memset(x,0,sizeof(x))
#define ll long long
namespace IO{
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T>void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);
while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
char sr[<<],z[]; int C1=-,Z;
template<class T>void wer(T x)
{
if (x<) sr[++C1]='-',x=-x;
while (z[++Z]=x%+,x/=);
while (sr[++C1]=z[Z],--Z);
}
IL void wer1()
{
sr[++C1]=' ';
}
IL void wer2()
{
sr[++C1]='\n';
}
template<class T>IL void maxa(T &x,T y) { if (x<y) x=y;}
template<class T>IL void mina(T &x,T y) { if (x>y) x=y;}
template<class T>IL void MAX(T x,T y){ return x>y?x:y;}
template<class T>IL void MIN(T x,T y){ return x<y?x:y;}
};
using namespace IO;
const int N=3e5*;
const double ee=1.0000000000;
const double pi=acos(-1.0);
struct cp{
double a,b;
cp operator +(const cp o) const
{
return (cp){o.a+a,o.b+b};
}
cp operator -(const cp o) const
{
return (cp){a-o.a,b-o.b};
}
cp operator *(const cp o) const
{
return (cp){a*o.a-b*o.b,b*o.a+a*o.b};
}
}a[N],b[N],w[N];
int n,m,l,r[N],mo,mo2,mo3,x1[N],x2[N];
int fsp(int x,int y)
{
ll now=;
while (y)
{
if (y&) now=now*x%mo;
y>>=; x=1ll*x*x%mo;
}
return now;
}
void fft_init()
{
l=; n=; while (n<=m) n<<=,l++;
for (int i=;i<n;i++)
{
w[i]=(cp){cos(pi*i/n),sin(pi*i/n)};
r[i]=(r[i/]/)|((i&)<<(l-));
}
}
void fft_clear()
{
rep(i,,n-) a[i].a=a[i].b=b[i].a=b[i].b=;
}
void fft(cp *a,int o)
{
for (int i=;i<n;i++) if (i>r[i]) swap(a[i],a[r[i]]);
for (int i=;i<n;i*=)
for (int j=;j<n;j+=(i*))
{
cp *x1=a+j,*x2=a+i+j;
for (int k=;k<i;k++,x1++,x2++)
{
cp W=w[n/i*k]; W.b*=o;
cp x=*x1,y=(*x2)*W;
*x1=x+y,*x2=x-y;
}
}
if (o==-) rep(i,,n-) a[i].a/=n;
}
cp a1[N],a2[N],a3[N],b1[N],b2[N];
void getcj(int *A,int *B,int len)
{
m=*len; fft_init();
rep(i,,len-)
{
a1[i].a=A[i]/mo2,a2[i].a=A[i]%mo2;
b1[i].a=B[i]/mo2,b2[i].a=B[i]%mo2;
}
fft(a1,); fft(a2,); fft(b1,); fft(b2,);
rep(i,,n-)
{
a3[i]=a1[i]*b1[i];
a1[i]=a1[i]*b2[i]+a2[i]*b1[i];
b2[i]=a2[i]*b2[i];
}
fft(a3,-); fft(a1,-); fft(b2,-);
rep(i,,len-)
{
B[i]=((ll)(a3[i].a+0.5)%mo*mo3+(ll)(a1[i].a+0.5)%mo*mo2+(ll)(b2[i].a+0.5))%mo;
B[i]=(B[i]+mo)%mo;
}
rep(i,,n)
{
a1[i].a=a1[i].b=a2[i].a=a2[i].b=a3[i].a=a3[i].b=;
b1[i].a=b1[i].b=b2[i].a=b2[i].b=;
}
}
int C[N];
IL void getinv(int *A,int *B,int len)
{
if (len==) {B[]=fsp(A[],mo-); return;}
getinv(A,B,(len+)>>);
rep(i,,len-) C[i]=A[i];
getcj(B,C,len); getcj(B,C,len);
rep(i,,len-) B[i]=((2ll*B[i]-C[i])%mo+mo)%mo;
}
IL void getdao(int *A,int *B,int len)
{
for (int i=;i<len-;i++)
B[i]=1ll*A[i+]*(i+)%mo;
B[len-]=;
}
IL void getjf(int *A,int *B,int len)
{
for (int i=;i<len;i++)
B[i]=1ll*A[i-]*fsp(i,mo-)%mo;
B[]=;
}
int C[N],D[N];
IL void getln(int *A,int *B,int len)
{
getdao(A,C,len);
getinv(A,D,len);
getcj(C,D,len);
getjf(D,B,len);
}
void getexp(int *A,int *B,int len)
{
if (len==) {B[]=; return;}
getexp(A,B,(len+)>>);
getln(B,C,len);
rep(i,,len-) C[i]=((-C[i]+A[i])%mo+mo)%mo;
C[]=(C[]+)%mo;
getcj(C,B,len);
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
int n1;
read(n1); read(mo); mo2=3e4; mo3=mo2*mo2;
x1[]=;
rep(i,,n1) read(x1[i]);
getln(x1,x2,n1+);
rep(i,,n1)
{
for (int j=;j*i<=n1;j++)
x2[i*j]=(x2[i*j]-1ll*x2[i]*fsp(j,mo-))%mo;
}
int cnt=;
rep(i,,n1) if (x2[i]) cnt++;
wer(cnt); wer2();
rep(i,,n1) if (x2[i]) wer(i),wer1();
wer2();
fwrite(sr,,C1+,stdout);
return ;
}
#updata 12.14
使用我优秀的常数的新模板他就过了
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define me(x) memset(x,0,sizeof(x))
#define ll long long
namespace IO{
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;
}
template<class T>void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);
while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
char sr[<<],z[]; int C1=-,Z;
template<class T>void wer(T x)
{
if (x<) sr[++C1]='-',x=-x;
while (z[++Z]=x%+,x/=);
while (sr[++C1]=z[Z],--Z);
}
IL void wer1()
{
sr[++C1]=' ';
}
IL void wer2()
{
sr[++C1]='\n';
}
template<class T>IL void maxa(T &x,T y) { if (x<y) x=y;}
template<class T>IL void mina(T &x,T y) { if (x>y) x=y;}
template<class T>IL void MAX(T x,T y){ return x>y?x:y;}
template<class T>IL void MIN(T x,T y){ return x<y?x:y;}
};
using namespace IO;
const int N=3e5*;
const double ee=1.0000000000;
const double pi=acos(-1.0);
struct cp{
double a,b;
cp operator +(const cp o) const
{
return (cp){o.a+a,o.b+b};
}
cp operator -(const cp o) const
{
return (cp){a-o.a,b-o.b};
}
cp operator *(const cp o) const
{
return (cp){a*o.a-b*o.b,b*o.a+a*o.b};
}
}a[N],b[N],c[N],d[N];
int n,m,l,r[N],mo,x1[N],x2[N];
IL int fsp(int x,int y)
{
ll now=;
while (y)
{
if (y&) now=now*x%mo;
x=1ll*x*x%mo;
y>>=;
}
return now;
}
IL void clear()
{
for (int i=;i<=n;i++) a[i].a=a[i].b=b[i].a=b[i].b=c[i].a=c[i].b=d[i].a=d[i].b=;
}
cp *w[N],tmp[N*];
int p;
IL void init()
{
cp *now=tmp;
for (int i=;i<=p;i<<=)
{
w[i]=now;
for (int j=;j<i;j++) w[i][j]=(cp){cos(pi*j/i),sin(pi*j/i)};
now+=i;
}
}
IL void fft_init()
{
l=; for (n=;n<=m;n<<=) l++;
for (int i=;i<n;i++) r[i]=(r[i/]/)|((i&)<<(l-));
}
void fft(cp *a,int o)
{
for (int i=;i<n;i++) if (i>r[i]) swap(a[i],a[r[i]]);
for (int i=;i<n;i<<=)
for (int j=;j<n;j+=(i*))
{
cp *x1=a+j,*x2=a+i+j,*W=w[i];
for (int k=;k<i;k++,x1++,x2++,W++)
{
cp x=*x1,y=(cp){(*W).a,(*W).b*o}*(*x2);
*x1=x+y,*x2=x-y;
}
}
if (o==-) for(int i=;i<n;i++) a[i].a/=n;
}
IL void getcj(int *A,int *B,int len)
{
rep(i,,len)
{
A[i]=(A[i]+mo)%mo,B[i]=(B[i]+mo)%mo;
}
for (int i=;i<len;i++)
{
a[i]=(cp){A[i]&,A[i]>>};
b[i]=(cp){B[i]&,B[i]>>};
}
m=len*; fft_init();
fft(a,); fft(b,);
for (int i=;i<n;i++)
{
int j=(n-)&(n-i);
c[j]=(cp){0.5*(a[i].a+a[j].a),0.5*(a[i].b-a[j].b)}*b[i];
d[j]=(cp){0.5*(a[i].b+a[j].b),0.5*(a[j].a-a[i].a)}*b[i];
}
fft(c,); fft(d,);
double inv=ee/n;
rep(i,,n) c[i].a*=inv,c[i].b*=inv;
rep(i,,n) d[i].a*=inv,d[i].b*=inv;
rep(i,,len)
{
ll a1=c[i].a+0.5,a2=c[i].b+0.5;
ll a3=d[i].a+0.5,a4=d[i].b+0.5;
B[i]=(a1+((a2+a3)%mo<<)+((a4%mo)<<))%mo;
}
clear();
}
int C[N],D[N];
IL void getinv(int *A,int *B,int len)
{
if (len==) {B[]=fsp(A[],mo-); return;}
getinv(A,B,(len+)>>);
rep(i,,len-) C[i]=A[i];
getcj(B,C,len); getcj(B,C,len);
rep(i,,len-) B[i]=((2ll*B[i]-C[i])%mo+mo)%mo;
}
IL void getdao(int *A,int *B,int len)
{
for (int i=;i<len-;i++)
B[i]=1ll*A[i+]*(i+)%mo;
B[len-]=;
}
IL void getjf(int *A,int *B,int len)
{
for (int i=;i<len;i++)
B[i]=1ll*A[i-]*fsp(i,mo-)%mo;
B[]=;
}
IL void getln(int *A,int *B,int len)
{
getdao(A,C,len);
getinv(A,D,len);
getcj(C,D,len);
getjf(D,B,len);
}
void getexp(int *A,int *B,int len)
{
if (len==) {B[]=; return;}
getexp(A,B,(len+)>>);
getln(B,C,len);
rep(i,,len-) C[i]=((-C[i]+A[i])%mo+mo)%mo;
C[]=(C[]+)%mo;
getcj(C,B,len);
}
int main()
{
freopen("10.in","r",stdin);
freopen("1.out","w",stdout);
int n1;
read(n1); read(mo);
x1[]=;
rep(i,,n1) read(x1[i]);
p=(n1+)<<; init();
getln(x1,x2,n1+);
rep(i,,n1)
{
for (int j=;j*i<=n1;j++)
x2[i*j]=(x2[i*j]-1ll*x2[i]*fsp(j,mo-))%mo;
}
int cnt=;
rep(i,,n1) if (x2[i]) cnt++;
wer(cnt); wer2();
rep(i,,n1) if (x2[i]) wer(i),wer1();
wer2();
fwrite(sr,,C1+,stdout);
return ;
}