自动搬运

查看原文

来自洛谷，原作者为

	b__b 废物

搬运于2025-08-24 23:13:46，当前版本为作者最后更新于2025-04-18 20:32:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

容斥原理

对于有两个集合的容斥原理小图片，我们有这个公式：$|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$。