Codeforces757E.Bash Plays With Functions(积性函数 DP)
(Description)
q次询问，每次给定r,n，求(F_r(n))。
[ f_0(n)=sum_{u imes v=n}[(u,v)=1]\
f_{r+1}(n)=sum_{u imes v=n}frac{f_r(u)+f_r(v)}{2}]
(Solution)
首先将(f_r)的式子化为
[f_{r+1}(n)=sum_{d|n}f_r(d)
]
即(f_{r+1}(n))为(f_r(n))与(g(n)=1)的狄利克雷卷积。
因为n的所有质因子之间对(f_0(n))的贡献是独立的，所以显然(f_0(n))为积性函数（为什么我还是不懂。。），那么(f_r(n))也为积性函数。
于是可以对每个质因子单独计算，这样狄利克雷卷积就可以化成求和
[f_{r+1}(p^k)=sum_{i=0}^kf_r(p^i)
]
（(p^k)的所有因子即(p^i,i=0,1,ldots,k)）
同时可以发现(f_0(p^k)=[k
eq 0]+1)，即(f_0(p^k))的值与因子p无关，只与次数有关。
那么DP，用(dp[i][j])表示(f_i(p^j))，则(dp[i][j]=sum_{k=0}^jdp[i-1][k])。
询问时对(n)分解质因数即可。
#include<cmath>
#include<cstdio>
#include<cctype>
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=1e6+3,M=21,mod=1e9+7,MAXIN=1<<18;
int r,n,f[N+3][21],Primes[100000],cnt;
char IN[MAXIN],*SS=IN,*TT=IN;
bool Not_Prime[N+3];
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
#define Mod(a) (a>=mod)?a-=mod:0
void Init()
{
// Not_Prime[1]=1;
for(int i=2;i<N;++i)
{
if(!Not_Prime[i]) Primes[++cnt]=i;
for(int j=1;j<=cnt&&Primes[j]*i<N;++j)
{
Not_Prime[i*Primes[j]]=1;
if(!(i%Primes[j])) break;
}
}
f[0][0]=1;//f_r(p^0)=1
for(int i=1;i<M;++i) f[0][i]=2;
for(int sum=0,i=1;i<N;++i,sum=0)
for(int j=0;j<M;++j)
{
sum+=f[i-1][j], Mod(sum);
f[i][j]+=sum, Mod(f[i][j]);
}
}
int Solve(int r,int n)
{
int ans=1,m=sqrt(n+0.5);
for(int i=1;i<=cnt&&Primes[i]<=m;++i)
{
if(n%Primes[i]) continue;
int t=0;
while(!(n%Primes[i])) n/=Primes[i],++t;
ans=1LL*ans*f[r][t]%mod;
}
if(n>1) ans=1LL*ans*f[r][1]%mod;//本身是个质数
return ans;
}
int main()
{
//#ifndef ONLINE_JUDGE
// freopen("757.in","r",stdin);
//#endif
Init();
int t=read(),r,n;
while(t--)
r=read(),n=read(),printf("%d
",Solve(r,n));
return 0;
}