codeforces757E. Bash Plays with Functions(狄利克雷卷积 积性函数)
codeforces757E. Bash Plays with Functions(狄利克雷卷积 积性函数)
attack
发布于 2018-07-27 15:23:09
发布于 2018-07-27 15:23:09
http://codeforces.com/contest/757/problem/E
题意
Sol
非常骚的一道题
首先把给的式子化一下，设$u = d$，那么$v = n / d$
$$f_r(n) = \sum_{d \mid n} \frac{f_{r - 1}(d) + f_{r - 1}(\frac{n}{d})}{2}$$
$$= \sum_{d\mid n} f_{r - 1}(d)$$
很显然，这是$f_r(n)$与$1$的狄利克雷卷积
根据归纳法可以证明$f_r(n)$为积性函数
我们可以对每个质因子分别考虑他们的贡献
考虑$f_0(p^k) = [k =0]+1$，与$p$是无关的，因此我们只要枚举$r$和$k$就好
$f_r(p^k) = \sum_{i = 0}^k f_{r - 1}(p^i)$
前缀和优化dp
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10, mod = 1e9 + 7;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int prime[MAXN], tot, vis[MAXN];
LL f[MAXN][22];
void GetPrime(int N) {
for(int i = 2; i <= N; i++) {
if(!vis[i]) prime[++tot] = i;
for(int j = 1; j <= N && i * prime[j] <= N; j++) {
vis[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
}
void Pre(int N, int M) {
f[0][0] = 1;//f[i][k] f_r(p^k)
for(int i = 1; i <= M; i++) f[0][i] = 2;
for(int r = 1; r <= N; r++) {
LL sum = 0;
for(int k = 0; k <= M; k++) {
sum += f[r - 1][k];
(f[r][k] += sum ) %= mod;
}
}
}
main() {
GetPrime(1e6 + 5);
Pre(1e6 + 5, 21);
int Q = read();
while(Q--) {
int r = read(), n = read();
LL ans = 1;
for(int i = 1; i <= tot && prime[i] <= sqrt(n); i++) {
if(n % prime[i]) continue;
int num = 0;
while(!(n % prime[i])) num++, n /= prime[i];
ans = 1ll * ans * (f[r][num]) % mod;
}
if(n > 1) ans = (1ll * ans * f[r][1]) % mod;
printf("%I64d\n", ans);
}
}
/*
*/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录