AT5310 [ABC162E] Sum of gcd of Tuples 题解

· · 题解

草，竟然不用整除分块。

不妨把题目一大堆西格玛写成这样：

ans=\sum_{1\le a_1,a_2,...,a_n\le k}\gcd_{i=1}^{n}\left(a_i\right)

然后由 id=\varphi *I：

\begin{aligned}ans&=\sum_{1\le a_1,a_2,...,a_n\le k}\gcd_{i=1}^{n}\left(a_i\right)\\&=\sum_{1\le a_1,a_2,...,a_n\le k}\;\sum\limits_{d\mid a_1,d\mid a_2,...,d\mid a_n}\varphi(d)\\&=\sum\limits_{d=1}^{k}\varphi(d)\left\lfloor\dfrac{k}{d}\right\rfloor^n\end{aligned}

然后这个就可以开始整除分块了，其实暴力也能过。

整除分块复杂度 O(\sqrt{n}\log k)。

#include <bits/stdc++.h>
#define int long long
namespace mystd {
    inline int read() {
        int w = 1, q = 0;
        char ch = ' ';
        while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
        if (ch == '-') w = -1, ch = getchar();
        while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();
        return w * q;
    }
    inline void write(int x) {
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace std;
using namespace mystd;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 100;
int n, k, tot, pr[maxn], v[maxn], phi[maxn];

int ksm(int p, int q) {
    int res = 1;
    while (q) {
        if (q & 1) res = res * p % mod;
        p = p * p % mod, q >>= 1;
    }
    return res;
}

void init(int lim) {
    phi[1] = 1;
    for (int i = 2; i <= lim; i++) {
        if (!v[i]) pr[++tot] = i, phi[i] = i - 1;
        for (int j = 1; j <= tot && i * pr[j] <= lim; j++) {
            v[i * pr[j]] = 1;
            if (i % pr[j] == 0) {
                phi[i * pr[j]] = phi[i] * pr[j];
                break;
            }
            phi[i * pr[j]] = phi[i] * phi[pr[j]];
        }
    }
    for (int i = 2; i <= lim; i++) phi[i] = (phi[i] + phi[i - 1]) % mod;
}

int calc(int n, int k) {
    int res = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        res = (res + (phi[r] - phi[l - 1] + mod) % mod * ksm(n / l, k)) % mod;
    }
    return res;
}

signed main() {
    k = read(), n = read();
    init(1e5);
    write(calc(n, k)), puts("");
    return 0;
}