【Codeforces 757E】Bash Plays with Functions

相关链接

题目传送门:http://codeforces.com/problemset/problem/757/E
官方题解:http://codeforces.com/blog/entry/49743

解题报告

这题窝萌需要打很多的表来发现以下规律:

Ⅰ. 设$x$的素因子种类数为$g(x)$那么$f_0(x)$等于$2^{g(x)}$
Ⅱ. 由规律Ⅰ可得,$f_0(x)$为积性函数,又$f_i(x)=f_{i-1} * 1(x)$,于是我们可用归纳证明得$f_i(x)$均为积性函数
Ⅲ. 设$p$为素数,$f_r(p^k)$与$p$无关,且满足递推式:$f_r(p^k)=\sum\limits_{i=0}^{k}{f_{r-1}(p^i)}$

于是我们预处理出$f_r(p^k)$
对于每次询问,使用积性函数的性质,拆成很多质因数的幂次来做可以辣!
时间复杂度:$O((q+r) \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000009;
const int MOD = 1000000007;

int tot,vis[N],pri[N],sur[N],g[N][21];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void prework() {
	for (int i=2;i<N;i++) {
		if (!vis[i]) pri[++tot] = i, sur[i] = i;
		for (int j=1;j<=tot&&i*pri[j]<N;j++) {
			vis[i*pri[j]] = 1; sur[i*pri[j]] = pri[j];
			if (i % pri[j] == 0) break;
		}
	}	
	g[0][0] = 1;
	for (int i=1;i<=20;i++) g[0][i] = 2;
	for (int i=1;i<N;i++) {
		for (int j=0;j<=20;j++) {
			g[i][j] = ((j? g[i][j-1]: 0) + g[i-1][j]) % MOD;
		}
	}
}	

inline int solve(int a, int b) {
	int ret = 1;
	for (int cnt=0,p=sur[b];b>1;cnt=0,p=sur[b]) {
		while (b % p == 0) b /= p, cnt++;
		ret = (LL)ret * g[a][cnt] % MOD;
	}
	return ret;
}

int main() { 
	prework();
	for (int T=read(),a,b;T;T--) {
		a = read(); b = read();
		printf("%d\n",solve(a,b));
	}
	return 0;
}