从数论函数杂讲.ppt的第16页，我们知道f[n][r]是积性函数。
显然f[r][p^a]与p无关（p是质数）
根据题意，我们知道f[r][p^a]=f[r][p^(a-1)]+f[r-1][p^a]，所以就预处理出f[r][p^a]，a∈[0,logn]
然后就能O(logn)求出f[r][n]辣。
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define rep(i,j,k) for(i=j;i<=k;++i) #define per(i,j,k) for(i=j;i>=k;--i) #define ll long long #define db double #define ldb long double #define pii pair<int,int> #define mkp make_pair #define X first #define Y second #define G c=getchar() const int N=1000000,L=20,MOD=1000000007; ll pri[N+1],vis[N+1],pk[N+1],ak[N+1],cnt,f[N+1][L+1],r,n,ans; ll add(ll x,ll y){ if((x+=y)>=MOD)x-=MOD; return x; } ll mul(ll x,ll y){ return x*y%MOD; } int main(){ ll i,j,y,_; rep(i,2,N){ if(!vis[i]){ pri[++cnt]=i; pk[i]=i;ak[i]=1; } for(j=1;j<=cnt&&(y=pri[j]*i)<=N;++j){ vis[y]=1; if(i%pri[j]==0){ pk[y]=pk[i]*pri[j]; ak[y]=ak[i]+1; break; } pk[y]=pri[j]; ak[y]=1; } } f[0][0]=1; rep(i,1,L)f[0][i]=2; rep(i,1,N){ f[i][0]=1; rep(j,1,L)f[i][j]=add(f[i-1][j],f[i][j-1]); } for(scanf("%lld",&_);_--;){ scanf("%lld%lld",&r,&n);ans=1; while(n>1){ ans=mul(ans,f[r][ak[n]]);n/=pk[n]; } printf("%lld\n",ans); } return 0; }
