题解：P12216 [蓝桥杯 2023 国 Java B] 互质

· · 题解

简单数论（运用容斥原理及快速幂）。

容斥原理

对于有两个集合的容斥原理小图片，我们有这个公式：|A \cup B|=|A|+|B|-|A \cap B|。

正文

~注意到~通过质因数分解可得 2023=7\times 17^2。

设 [1,2023^{2023}] 范围内有 n 个整数，则在这个范围内可以被 7 整除的数的数量为 \lfloor\frac{n}{7}\rfloor，可以被 17 整除的数的数量为 \lfloor\frac{n}{17}\rfloor，既可以被 7 整除又可以被 17 整除的数的数量为 \lfloor\frac{n}{7\times17}\rfloor。

因此答案为 n-\lfloor\frac{n}{7}\rfloor-\lfloor\frac{n}{17}\rfloor+\lfloor\frac{n}{7\times17}\rfloor（由容斥原理可得可以被 7 或 17 整除的数为 \lfloor \frac{n}{7} \rfloor+\lfloor\frac{n}{17}\rfloor-\lfloor\frac{n}{7\times17}\rfloor，再用 n 减去）。

但是 n 是一个极其巨大的数，因此我们会用到快速幂。

代码

下列给出 Java 与 C++ 代码。

Java

public class HuZhi {
    static final long MOD = 1000000007;
    static long pw(long b, long e) {
        long r = 1;
        while (e > 0) {
            if ((e & 1) == 1) r = r * b % MOD;
            b = b * b % MOD;
            e >>= 1;
        }
        return r;
    }
    public static void main(String[] args) {
        //a为2023^2023/7,因此可以表示为(2023/7)^2023*7^2022
        //下文同理，不再给出解释
        long n = pw(2023, 2023), a = pw(7, 2022) * pw(289, 2023) % MOD, b = pw(17,  2022) * pw(119, 2023) % MOD, c = pw(119, 2022) * pw(17,  2023) % MOD;
        System.out.print((n - a - b + c) % MOD);
    }
}

C++

#include <cstdio>
typedef long long ll;
const ll MOD = 1000000007;
ll pw(ll b, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}
int main() {
    ll n = pw(2023, 2023), a = pw(7, 2022) * pw(289, 2023) % MOD, b = pw(17,  2022) * pw(119, 2023) % MOD, c = pw(119, 2022) * pw(17,  2023) % MOD;
    printf("%lld", (n - a - b + c) % MOD);
    return 0;
}

答案为 640720414。