设 f0,n= f 0 , n = 将n分成两个互质的数的积的方案数。 fr,n=∑fr−1,u+fr−1,v2(uv=n) f r , n = ∑ f r − 1 , u + f r − 1 , v 2 ( u v = n ) 多组询问，每次给出 r,n r , n ，求 fr,n f r , n 对 109+7 10 9 + 7 取模。
今天男神出给我们做，因为太菜，考场口胡没时间写。 显然 f0,n=2num,num f 0 , n = 2 n u m , n u m 为n的不同质因子个数。 考虑 fr,n f r , n 的意义，显然可以枚举n的因数，那么他对答案最终的贡献就是，将该因数每一次乘一个数，在r次内变成n的方案数，所以可以枚举因数+组合数算贡献。这种做法在cf上T了。但过了男神数据。 %栋老师写法，发现没有必要枚举因数，只需要对每个不同质因数单独算出贡献，最后乘起来即可。具体代码，上面两种都给出来。 code：（TLE）
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #define LL long long using namespace std; const LL mod=1e9+7; bool v[1000010]; int prime[1000010],pr=0,r,n; LL bin[1000010],f[1000010],F[2000010],inv[2000010]; LL C(int m,int n) { if(n>m) return 0; return F[m]*inv[m-n]%mod*inv[n]%mod; } void pre() { memset(v,true,sizeof(v)); F[0]=F[1]=inv[0]=inv[1]=1; for(int i=2;i<=2000000;i++) F[i]=F[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod; for(int i=2;i<=2000000;i++) inv[i]=inv[i-1]*inv[i]%mod; for(int i=2;i<=1000000;i++) { if(v[i]) prime[++pr]=i,f[i]=1; for(int j=1;j<=pr&&i*prime[j]<=1000000;j++) { v[i*prime[j]]=false; if(i%prime[j]==0) {f[i*prime[j]]=f[i];break;} f[i*prime[j]]=f[i]+1; } } bin[0]=1;for(int i=1;i<=1000000;i++) bin[i]=bin[i-1]*2%mod; for(int i=1;i<=1000000;i++) f[i]=bin[f[i]]; } LL read() { LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct node{ int a,num; }a[25];int num; void dec(int x) { num=0;memset(a,0,sizeof(a)); for(int i=1;prime[i]*prime[i]<=x;i++) if(x%prime[i]==0) { a[++num].a=prime[i]; while(x%prime[i]==0) x/=prime[i],a[num].num++; } if(x!=1) a[++num].a=x,a[num].num=1; } LL ans=0; void dfs(int x,int s,LL t) { if(x>num) {ans=(ans+f[s]*t%mod)%mod;return;} for(int i=0;i<=a[x].num;i++) { dfs(x+1,s,t*C(r+a[x].num-i-1,r-1)%mod); s*=a[x].a; } } int main() { pre(); int T=read(); while(T--) { r=read();n=read(); if(r==0) {printf("%lld\n",f[n]);continue;} dec(n); ans=0;dfs(1,1,1LL); printf("%lld\n",ans); } }AC：
#include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<cmath> #include<ctime> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstdlib> #include<cstring> #include<climits> #include<complex> #include<iostream> #include<algorithm> #define ll long long #define inf 1e9 using namespace std; inline void read(int &x) { char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0'; } const int maxn = 1010000; const int mod = 1e9+7; inline void add(int &a,const int &b){a+=b;if(a>=mod)a-=mod;} int pw(int x,int k) { int re=1; for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) re=(ll)re*x%mod; return re; } int inv(int x){return pw(x,mod-2);} int p[maxn],pri,mp[maxn],pn[maxn]; int r0[maxn]; int s[maxn],invs[maxn]; void pre() { r0[1]=1; for(int i=2;i<maxn;i++) { if(!mp[i]) p[++pri]=i,mp[i]=i,pn[i]=1; for(int j=1,k=p[j]*i;k<maxn;j++,k=p[j]*i) { mp[k]=p[j]; if(i%p[j]==0) { pn[k]=pn[i]; break; } pn[k]=pn[i]+1; } r0[i]=(1ll<<pn[i])%mod; } s[0]=1; for(int i=1;i<maxn;i++) s[i]=(ll)s[i-1]*i%mod; invs[maxn-1]=inv(s[maxn-1]); for(int i=maxn-2;i>=0;i--) invs[i]=(ll)invs[i+1]*(i+1)%mod; } int C(const int n,const int m){return (ll)s[n]*invs[m]%mod*invs[n-m]%mod;} int t[maxn],tp,tu[maxn]; int m,r,n; int solve() { int re=1; for(int i=1;i<=tp;i++) { int tmp=0; for(int j=0;j<=t[i];j++) { int now=!j?1:2; if(j<t[i]) now=(ll)now*C(t[i]-j+1+r-2,r-1)%mod; add(tmp,now); } re=(ll)re*tmp%mod; } return re; } int main() { pre(); read(m); while(m--) { read(r),read(n); if(n<=0) { puts("0");continue; } if(!r) { printf("%d\n",r0[n]); continue; } if(n==1) { puts("1"); continue; } tp=0; int tmp=n; while(tmp>1) { int pi=mp[tmp]; t[++tp]=0; while(mp[tmp]==pi) tmp/=pi,t[tp]++; } printf("%d\n",solve()); } return 0; }