题目描述
定义两个函数 \(f, g: \{1, 2, \dots, n\} \rightarrow \mathbb Z\) 的狄利克雷卷积 \(f * g\) 为：
\]
我们定义 \(g = f^k\) 即 \(k\) 次幂为：
\]
在本题中，我们想要解决这个问题的逆问题：给你 \(g\) 和 \(k\)，你需要找到一个函数 \(f\) 使得 \(g = f^k\)。
另外，保证 \(g(1)=1\)，你需要保证 \(f(1)=1\)。所有的运算在 \(\mathbb F_p\) 上进行，其中 \(p = 998244353\)，这意味着狄利克雷卷积为 \((f*g)(n) = \left(\sum_{d|n} f(d)g(\frac nd)\right) \bmod p\)。
\(n\le 10^6\)
Sol
定义一个数论函数 \(f(n)\) 的狄利克雷生成函数是 \(F(x)=\sum_{n=1}^\infty f(n)n^x\)。
注意这个东西不是关于 \(x\) 的多项式（一开始我当成了多项式），然而它可以做多项式乘法，由于这个 \(a^x\cdot b^x \rightarrow (ab)^x\)，所以对于生成函数系数来说，相当于完成了两个数论函数的 狄利克雷卷积。
既然有类似多项式的性质，那么我们考虑 ln-exp 的方法求解 k 次根。
根据多项式 ln 的推导，有 \(B=\ln A\rightarrow B=\int {A'\over A}\)
除法可以用 狄利克雷除法 实现，那么我们只需要支持 导数和积分 运算即可。
考虑这个指数函数的求导法则 \(\displaystyle {\text{d} a^x\over \text{d}x}=a^x\ln a\)。
然而在正整数意义下没有 \(\ln\) 这种运算，然后做法是找一个运算性质跟 \(\ln\) 一样的东西来替代它，比如质因子个数函数 \(\text{cnt}_x\)（相同的算作多个），因为它满足 \(f(x)+f(y)=f(xy)\) 这样的性质。
于是可以实现一个对一个狄利克雷级数求对数函数的代码如下：
void ln(int n, int *a)
{
b[1] = 0;
for(int i = 2; i <= n; ++i)
b[i] = (ll)a[i] * cnt[i] % P;
for(int i = 2; i <= n; ++i)
{
for(int j = 2, k = i * j; k <= n; ++j, k += i)
b[k] = (b[k] - 1LL * b[i] * a[j]) % P;
b[i] = (1LL * b[i] * inv[cnt[i]] % P + P) % P;
}
for(int i = 1; i <= n; ++i)
a[i] = b[i];
}
由于 \(B=A^{1/k}=\exp {{\ln A} \over k}\)，那么只要先求 \(\ln\) 再 \(\exp\) 即可。
求指数函数也是类似的，整个代码如下，和暴力 \(O(n^2)\) 的普通多项式对数/指数函数非常相似。
#include<stdio.h>
typedef long long ll;
const int N = 1000005, P = 998244353;
int fexp(int a, int b)
{
ll x = 1, o = a;
for(; b; b >>= 1, o = o * o % P)
if(b & 1) x = x * o % P;
return x;
}
int n, K, a[N], b[N], inv[128], cnt[N];
bool np[N];
void init()
{
cnt[1] = 1;
for(int i = 2; i <= n; ++i)
if(!np[i])
{
cnt[i] = 1;
for(int j = 2, k = i * j; k <= n; j++, k += i)
{
np[k] = true;
if(!cnt[k] && cnt[j]) cnt[k] = cnt[j] + 1;
}
}
inv[1] = 1;
for(int i = 2; i < 128; ++i)
inv[i] = (ll)inv[P % i] * (P - P / i) % P;
}
void ln(int n, int *a)
{
b[1] = 0;
for(int i = 2; i <= n; ++i)
b[i] = (ll)a[i] * cnt[i] % P;
for(int i = 2; i <= n; ++i)
{
for(int j = 2, k = i * j; k <= n; ++j, k += i)
b[k] = (b[k] - 1LL * b[i] * a[j]) % P;
b[i] = (1LL * b[i] * inv[cnt[i]] % P + P) % P;
}
for(int i = 1; i <= n; ++i)
a[i] = b[i];
}
void exp(int n, int *a)
{
for(int i = 2; i <= n; ++i)
b[i] = (ll)a[i] * cnt[i] % P, a[i] = 0;
a[1] = 1;
for(int i = 1; i <= n; ++i)
{
a[i] = 1ll * a[i] * inv[cnt[i]] % P;
for(int j = 2, k = i * j; k <= n; ++j, k += i)
a[k] = (a[k] + 1LL * a[i] * b[j]) % P;
}
}
int main()
{
scanf("%d %d", &n, &K);
for(int i = 1; i <= n; ++i)
scanf("%d", a + i);
init();
K = fexp(K, P - 2);
ln(n, a);
for(int i = 1; i <= n; ++i) a[i] = 1ll * a[i] * K % P;
exp(n, a);
for(int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);
return 0;
}