题解 | E Sum of gcd of Tuples (Hard)

E.Sum of gcd of Tuples (Hard)

定义:

$f(d)f(d)$为$gcd(A_1,A_2,A_3,\mathrm{.}\mathrm{.},A_n)=dgcd(A\_1,A\_2,A\_3,..,A\_n)=d$的方案数

$F(d)F(d)$为$gcd(A_1,A_2,A_3,\mathrm{.}\mathrm{.},A_n)gcd(A\_1,A\_2,A\_3,..,A\_n)$为$dd$的倍数的方案数

显然有，

莫比乌斯反演得

其中$F(d^{\mathrm{\prime }})F(d\text{'})$的方案数实际为满足条件$[d^{\mathrm{\prime }}\mathrm{\mid }{A}_1,d^{\mathrm{\prime }}\mathrm{\mid }{A}_2,\mathrm{.}\mathrm{.}\mathrm{.}{d}^{\mathrm{\prime }}\mathrm{\mid }{A}_n{]}^{\mathrm{\prime }}[d\text{'}|A\_1,d\text{'}|A\_2,...d\text{'}|A\_n]\text{'}$的方案数，由于$A_{i}A\_i$的范围为$[1,k][1,k]$，故每个数实际上只能选择$\lfloor \frac{k}{d^{\mathrm{\prime }}}\rfloor \backslash lfloor\; \backslash frac\{k\}\{d\text{'}\}\; \backslash rfloor$个，总的方案数就是$\lfloor \frac{k}{d^{\mathrm{\prime }}}{\rfloor }^n\backslash lfloor\; \backslash frac\{k\}\{d\text{'}\}\; \backslash rfloor^n$

则最终的答案可表示为

枚举$[1-k][1-k]$倍数复杂度$O(nlog(n))O(nlog(n))$,照着公式写就行了。

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7;
bool vis[N];
int Primes[N], mbux[N], cnt;
ll fpow[N];
ll ksm(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) {
            ans = ans * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}
void get_mbux(int n) {
    mbux[1] = 1;
    for (int i = 2; i <= n; i ++ ) {
        if(!vis[i]) {
            Primes[++ cnt] = i;
            mbux[i] = -1;
        }
        for (int j = 1; j <= cnt && i * Primes[j] <= n; j ++ ) {
            vis[i * Primes[j]] = 1;
            if(i % Primes[j] == 0) {
                mbux[i * Primes[j]] = 0; 
                break;
            }
            mbux[i * Primes[j]] = - mbux[i];
        }
    }
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i ++ ) {
        fpow[i] = ksm(i, n);
    }
    get_mbux(k);
    ll res = 0;
    for (int i = 1; i <= k; i ++ ) {
        ll temp = 0;
        for (int j = i; j <= k; j += i) {
            temp = (temp + mbux[j/i] * fpow[k/j] % mod + mod) % mod;
        }
        res = (res + temp * i % mod + mod) % mod;
    }
    printf("%lld", res);
}