相关链接
题目传送门: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; }