Atcoder ABC 162E（数学，计数）

发现我们可以根据 $\gcd$ 的值进行枚举，我们设 $\gcd(a_1,a_2,…,a_N) = x$ 的序列数量为 $d_x$，则有：

$d_1 = K^N - d_2 - d_3 - … - d_k$

那么 $d_2$ 呢？我们发现如果 $\gcd(a_1,a_2,…,a_N) = 2$，则所有的 $a_i$ 必然为 2的倍数，所以每个位置上有 $\frac{K}{2}$ 种选法，即：

$d_2 = (\frac{K}{2})^N - d_4 - d_6 - … - d_{\frac{K}{2} \times 2}$

同理有：

$d_3 = (\frac{K}{3})^N - d_6 - d_9 - … - d_{\frac{K}{3} \times 3}$

…

$d_K = 1$

这样，直接用一个 dp[] 记录一下 $d_x$ 的值，然后倒着枚举，暴力计算即可。

最终的答案为 $\sum\limits_{i=1}^K i \times dp[i]$

时间复杂度：$T(K) = K + \frac{K}{2} + \frac{K}{3} + … + \frac{K}{K} = K(1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{K})$

发现这个是 harmonic series 的和，复杂度大概为： $1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{K} = O(\log k)$

所以最终时间复杂度是 $O(K\log K)$

using namespace std;
#include <bits/stdc++.h>

const int mod = 1e9+7;
const int maxn = 1e5+5;

int n,k;
ll dp[maxn], ans = 0;
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) (res *= a) %= mod;
        b >>= 1;
        (a *= a) %= mod;
    }
    return res;
}

int main() {
    cin >> n >> k;
    for (int i = k; i >= 1; i--) {
        ll d = 0;
        for (int j = 2; i * j <= k; j++) {
            d += dp[i*j];
        }
        d %= mod;

        ll r = qpow(k/i, n);
        dp[i] = (r-d+(ll)mod) % mod;

        ans = (ans + (ll)(i) * (ll)(dp[i])) % mod;
    }
    cout << ans << endl;
}