题目链接：Luogu 5106

善良的 dkw 决定直接告诉你题面：

$$ \prod_{i_1 = 1} ^ n \prod_{i_2 = 1} ^ n \cdots\prod_{i_k = 1} ^ n \varphi(\operatorname{lcm}(i_1, i_2, \cdots, i_k)) $$

请你求上述式子，答案对 $10 ^ 9 + 7$ 取模。

其中 $\operatorname{lcm}(i_1, i_2, \cdots, i_k)$ 表示这 $k$ 个数的最小公倍数。特别地，一个数的 $\operatorname{lcm}$ 是自身。

数据范围：$1\le n,k\le 10^6$。

Solution

由于欧拉函数是积性函数，于是我们对每个质因子分别求解。

考虑一个质因子的若干次幂的贡献。设当前考虑的质因子为 $p$，指数为 $c$，有 $m$ 个 $k$ 元组的 $\operatorname{lcm}$（假设为 $x$） 满足 $p^c\mid x$ 且 $p^{c+1}\not\mid x$（换言之，这 $k$ 个数中质因子 $p$ 指数的最大值为 $c$），则 $p^c$ 对答案的贡献为 $\varphi(p^c)^m$。

那么我们怎么求出这个 $m$ 呢？单单考虑一个 $p^c$ 比较麻烦，我们考虑容斥。

• 在 $1$ 到 $n$ 中，是 $p^1,p^2,\cdots,p^c$ 任意一者的倍数，但不是 $p^{c+1}$ 的倍数的有 $n - \left\lfloor\frac{n}{p^{c+1}}\right\rfloor$ 个。
• 在 $1$ 到 $n$ 中，是 $p^1,p^2,\cdots,p^{c-1}$ 任意一者的倍数，但不是 $p^c$ 的倍数的有 $n - \left\lfloor\frac{n}{p^c}\right\rfloor$。

那么满足条件的 $k$ 元组，要求这 $k$ 个数都满足第一个条件，不都满足第二个条件。于是有 $m = \left(n - \left\lfloor\frac{n}{p^{c+1}}\right\rfloor\right) ^ k - \left(n - \left\lfloor\frac{n}{p^{c}}\right\rfloor\right) ^ k$。

分析一下复杂度。质数一共有 $\mathcal O\left(\frac{n}{\log n}\right)$ 个，枚举指数的复杂度为 $\mathcal O(\log n)$，快速幂的复杂度为 $\mathcal O(\log n)$。故总复杂度为 $\mathcal O(n\log n)$，可以通过本题。

时间复杂度：$\mathcal O(n\log n)$。

Code

#include <cstdio>

const int N = 1e6 + 5;
const int mod = 1e9 + 7, phiMod = 1e9 + 6;

int n, k, tot, p[N], phi[N];
bool flg[N];

void sieve(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!flg[i]) {
            p[++tot] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {
            flg[i * p[j]] = true;
            if (i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            } else {
                phi[i * p[j]] = phi[i] * phi[p[j]];
            }
        }
    }
}
int sub(int x, int y, int mod) {
    return x < y ? x - y + mod : x - y;
}
int pow(int x, int p, int mod) {
    int ans = 1;
    for (; p; p >>= 1, x = 1LL * x * x % mod) {
        if (p & 1) ans = 1LL * ans * x % mod;
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &k);
    sieve(n);
    int ans = 1;
    for (int i = 1; i <= tot; i++) {
        for (long long j = p[i]; j <= n; j *= p[i]) {
            int cnt = sub(pow(n - n / j / p[i], k, phiMod), pow(n - n / j, k, phiMod), phiMod);
            ans = 1LL * ans * pow(phi[j], cnt, mod) % mod;
        }
    }
    printf("%d\n", ans);
    return 0;
}