Description

题目链接

题目大意:给定 $n, k$,求

$$ \sum \limits_{a_1=1}^k \sum \limits_{a_2 = 1}^k \cdots \sum \limits_{a_n = 1}^k \gcd(a_1, a_2, \cdots a_n) \bmod 10^9 + 7 $$

的值。

Solution

考虑枚举公约数 $d | a_1, d | a_2, \cdots, d | a_n$,在不考虑最小公约数的情况下,这样的序列共有 $(\lfloor \dfrac{k}{d} \rfloor)^n$ 个。

事实上,在加上了最小的限制后,这个式子并不成立,但我们可以通过一些方法将多余的部分减去,也就是利用容斥原理。

设 $f(i)$ 表示最小公约数为 $i$ 时的序列个数,那么每次让 $f(i) = (\lfloor \dfrac{k}{i} \rfloor)^n$,然后让 $f(i)$ 减去 $\sum \limits_{j = 2}^{\lfloor \frac{n}{i} \rfloor} f(ij)$ 即可。

最后的答案为 $\sum if(i)$。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef long long LL;
typedef unsigned long long uLL;

const LL mod = 1e9 + 7;

LL f[100010];
LL n, k, ans;

LL qPow(LL a, LL b) {
    LL s = 1;
    for (; b; b >>= 1LL, a = a * a % mod)    if (b & 1LL)    s = s * a % mod;
    return s;
}

int main() {
    read(n), read(k);
    for (int i = k; i; --i) {
        f[i] = qPow(k / i, n);
        for (int j = i + i; j <= k; j += i) {
            f[i] -= f[j];
            f[i] = ((f[i] % mod) + mod) % mod;
        }
    }
    for (int i = 1; i <= k; ++i)    ans = (ans + f[i] * i) % mod;
    printf("%lld\n", ans);
    return 0;
}
Last modification:November 8th, 2021 at 04:12 am