狄利克雷卷积即乘法卷积$f_n = \sum \limits_{d\mid n} g_dh_{\frac{n}{d}}$两个积性函数的狄利克雷卷积仍然积性
Dirichlet k-th root
给定f，令$g^k = f$，求g此处乘法为狄利克雷卷积有结论$f^{mod} = \epsilon$，因而$f^{mod+1} = f$，尝试找一个x，使得$x * k = p * mod+1$，这样$f^x$即为答案。$x=inv(k)$即可由于狄利克雷卷积具有结合律，套一个快速幂
P4714 「数学」约数个数和
求$f_n = \sum \limits_{i_1\mid n}\sum \limits_{i_2\midi_1} \dots \sum \limits_{i_k\mid i_{k-1}} 1$
$n \leq 10^{18},k \leq 10^{18}$
上面这个求和形式可以转化成狄利克雷卷积的形式令$g_i = 1$，则$f = \epsilon^k * g$然而这里数字太大，做不了这是一个积性函数，所以对n质因数分解后考虑单个素因子的幂次的值（这里要pollard-rho）对于$f_{p^x}$，我们相当于枚举了所有满足$x_1+x_2+\dots + x_k \leqx$，其中$x_i \geq 0$的x的组合，根据插板法其值为$\binom{x+k}{k}$，由于幂次不会很大，可以转化成$\binom{x+k}{x}$，暴力计算即可
hdu5628 Clarke and math
求$f_n = \sum \limits_{i_1\mid n}\sum \limits_{i_2\midi_1} \dots \sum \limits_{i_k\mid i_{k-1}}g_{i_k}$
$n \leq 10^5, k\leq 10^5$
这题就是把上题的1换成了$kg_{i_k}$显然的做法就是狄利克雷卷积加快速幂这边考虑仿照上一题的做法，令$h_i$表示$g_j$转移给$jf_{ij}$的贡献，如果能算出$h_i$，那么$O(n\log n)$枚举倍数即可解决这同样是个积性函数，考虑$h_{p^x}$，相当于枚举了所有满足$x_1+x_2+\dots + x_k = x$，其中$x_i \geq 0$的x的组合，根据插板法值为$\binom{x+k-1}{x}$这里n很小，所以可以利用素数筛$O(n)$求得该积性函数h所以总复杂度是$O(n\log n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7, up = 2e5;
int fac[N], ifac[N], f[N], g[N], h[N];
int n, k, pr[N];
bool vis[N];
int fpw(int a, int b)
{
int ans = 1;
while(b)
{
if(b&1) ans = 1ll*ans*a%mod;
a = 1ll*a*a%mod;
b >>= 1;
}
return ans;
}
void init(int n)
{
fac[0] = 1;
for(int i=1; i<=n; i++) fac[i] = 1ll*i*fac[i-1]%mod;
ifac[n] = fpw(fac[n], mod-2);
for(int i=n-1; i>=0; i--) ifac[i] = 1ll*(i+1)*ifac[i+1]%mod;
}
int comb(int a, int b)
{
if(a<0||b<0||a<b) return 0;
return 1ll*fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}
void get(int n)
{
h[1] = 1;
for(int i=2; i<=n; i++)
{
if(!vis[i]) h[i] = k, pr[++pr[0]] = i;
for(int j=1; j<=pr[0]&&1ll*pr[j]*i<=n; j++)
{
vis[pr[j]*i] = 1;
if(i%pr[j]==0)
{
int tmp = i/pr[j], cnt = 2;
while(tmp%pr[j]==0) ++cnt, tmp /= pr[j];
h[pr[j]*i] = 1ll*h[tmp]*comb(cnt+k-1, cnt)%mod;
break;
}
else h[pr[j]*i] = 1ll*h[i]*h[pr[j]]%mod;
}
}
}
void solve()
{
scanf("%d%d", &n, &k);
for(int i=1; i<=n; i++) scanf("%d", f+i), g[i] = 0;
get(n);
for(int i=1; i<=n; i++)
for(int j=1; i*j<=n; j++)
g[i*j] = (g[i*j] + 1ll*f[i]*h[j])%mod;
for(int i=1; i<=n; i++) printf("%d%c", g[i], " \n"[i==n]);
}
int main()
{
init(up);
int _; scanf("%d", &_);
while(_--) solve();
return 0;
}
|