可以很容易推到
f_r(n) = sigema (d|n) f_r-1(d)
f_0(n) = 2^(n的质因子个数)
然后就不知道怎么办了
这是一个积性函数的应用小技巧
看出来f_0是一个积性函数,那么f_r也是积性函数
证明积性函数可以把表达式拆成关于质因子的多少次幂的式子,如果各个质因子互相独立就是积性函数
知道是积性函数后我们只需要考虑根基也就是f_r( p^t ) 时候的取值,我们可以预处理
然后观察式子,这个式子右边就相当于f_r-1 * 1 (n) *表示卷积
推一推式子可以发现,设f[i][j]表示f_i(p^j)
那么f[i][j]=sigema (k=0 to j) f[i-1][k]
前缀和优化即可
每次询问的时候暴力把n分解质因数再乘上相应答案
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long
#define maxn 1000001
#define maxm 22
using namespace std;
int q,r,n,minp[maxn],pri[maxn],cnt;
int f[maxn][maxm],sum[maxn][maxm];
bool vis[maxn];
const int mod=1e9+7;
inline int rd(){
int x=0,f=1;char c=' ';
while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();
while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();
return x*f;
}
inline void pre(){
for(int i=2;i<maxn;i++){
if(!vis[i]) pri[++cnt]=i,minp[i]=i;
for(int j=1;j<=cnt && i*pri[j]<maxn;j++){
vis[i*pri[j]]=1;
minp[i*pri[j]]=pri[j];//每个数的最小质因子
if(i%pri[j]==0) break;
}
}
}
int main(){
q=rd(); pre();
f[0][0]=sum[0][0]=1;//n=1特殊考虑
for(int i=1;i<maxm;i++)
f[0][i]=2,sum[0][i]=sum[0][i-1]+f[0][i];//前缀和优化
for(int i=1;i<maxn;i++){
for(int j=0;j<maxm;j++) f[i][j]=sum[i-1][j];
sum[i][0]=f[i][0];
for(int j=1;j<maxm;j++)
sum[i][j]=(sum[i][j-1]+f[i][j])%mod;
}
while(q--){
r=rd(); n=rd();
LL ans=1;
while(n>1){
int t=minp[n],j=0;//每次把最小的素数拆出来
while(n%t==0) n/=t,j++;
(ans*=f[r][j])%=mod;
}
printf("%lld\n",ans);
}
return 0;
}