NC229748 - Sum of gcd of Tuples (Hard)

题意

给你, ，让你求

数据范围

前置知识

莫比乌斯反演

思路

我们可以将题目给定的公式转换成下列形式：

我们可以设

接着设，可以发现表示是倍数的方案数

那么其实可以写成, 那么

接着根据莫比乌斯反演知道:

那么最终答案就是:

代码

/**
 *    author: andif
 *    created: 30.09.2023 16:15:06
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const db eps = 1e-9;
const int mod = 1e9 + 7;

int calc_f (int p, int a) {
    return a > 1 ? 0 : -1;
}

vi get_mo(int n) {
    vi mo(n + 1);
    vi p, is_p(n + 1, 1), cnt(n + 1);
    mo[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (is_p[i]) {
            mo[i] = -1;
            cnt[i] = 1;
            p.eb(i);
        }
        for (int j = 0; j < sz(p) && i * p[j] <= n; ++j) {
            int k = i * p[j];
            is_p[k] = 0;
            if (i % p[j] == 0) {
                cnt[k] = cnt[i] + 1;
                mo[k] = mo[i] / calc_f(p[j], cnt[i]) * calc_f(p[j], cnt[k]);
                break;
            }
            mo[k] = mo[i] * mo[p[j]];
            cnt[k] = 1;
        }
    }
    return mo;
}

int get_x_mo(int x) {
    if (x == 1) return 1;
    int p_c = 0;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            p_c++;
            int c = 0;
            while(x % i == 0) {
                c++;
                x /= i;
            }
            if (c > 1) return 0;
        }
    }
    if (x > 1) p_c++;
    return p_c & 1 ? -1 : 1;
}

int kpow(int a, int b) {
    int ret = 1;
    while(b) {
        if (b & 1) {
            ret = (1ll * ret * a) % mod;
        }
        a = (1ll * a * a) % mod;
        b >>= 1;
    }
    return ret;
}

int main() {
    qc;
    int n, k; cin >> n >> k;
    vi mo = get_mo(k);
    // rep(i, 1, k + 1) {
    //     if (mo[i] == get_x_mo(i)) de(i);
    //     assert(mo[i] == get_x_mo(i));
    // }
    vi f(k + 1);
    for (int i = 1; i <= k; ++i) {
        for (int j = 1; j * i <= k; ++j) {
            int m = i * j;
            f[i] = (f[i] + 1ll * mo[j] * kpow(k / m, n) % mod)% mod;
            if (f[i] < 0) f[i] += mod;
        }
    }
    int ans = 0;
    for (int i = 1; i <= k; ++i) {
        ans = (ans + 1ll * i * f[i] % mod) % mod;
    }
    cout << ans << '\n';
    return 0;
}