CF757E

CF757E Bash Plays with Functions

(f_r(n):)

在(r=0)，(p*q=n)且(gcd(p,q)=1)的有序对((p,q))个数

在(rge1)，(f_r(n)=largesumlimits_{u*v=n}frac{f_{r-1}(u)+f_{r-1}(v)}2)

(r=0)

因为(a*b=n)，(gcd(a,b)=1)，(a)和(b)平分了(n)的所有质因子

把(large p_i^{k_i})分成两份，方案数为(2^{w(n)})，(w(n))为(n)的质因子个数，(f_0(n)=2^{w(n)})

显然(f_0)为积性函数

(rge1)

变一个式子(large f_r(n)=sumlimits_{d|n}frac{f_{r-1}(d)+f_{r-1}(frac nd)}2)，(d)和(largefrac nd)对称的

把分母(2)打掉，(f_r(n)=largesumlimits_{d|n}f_{r-1}(d))

这是个狄利克雷卷积式子，(f_r=f_{r-1}×1) (f_r)是积性函数

(f_r(n)=prod f_r(p^{k_i}))

const int N = 1e6 + 5,K = 20,mod = 1e9 + 7;
int dp[N][K],sum[K] = {1},low[N];
void getprime(){
	for(int i = 2;i < N;++i)
		if(!low[i])
			for(int j = i;j < N;j += i) low[j] = i;
}
void init(){
	getprime();
	for(int i = 0;i < N;++i) dp[i][0] = 1;
	for(int i = 1;i < K;++i)
		dp[0][i] = 2,sum[i] = sum[i-1] + dp[0][i];
	for(int i = 1;i < N;++i)
		for(int j = 1;j < K;++j){
			dp[i][j] = sum[j]; sum[j] = (sum[j - 1] + dp[i][j]) % mod;
		}
}
ll ans = 1;
int main(){
	init(); int Q,r,n; Q = read();
	while(Q--){
		r = read(); n = read();
		ans = 1;int cnt,p;
		while(n != 1){
			cnt = 0;p = low[n];
			while(!(n % p)) ++cnt, n /= p;
			ans = ans * dp[r][cnt] % mod;
		}
		printf("%d",ans); putchar('
');
	}
}