[JOI2025 预选赛 R1H3] 不可兼或的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求统计 $1$ ~1~ 到 $N$ ~N~ 之间只能被 $A$ ~A~ 与 $B$ ~B~ 之一整除的整数的个数。核心解法是容斥：分别数出 $A$ ~A~ 的倍数与 $B$ ~B~ 的倍数，再减去同时被两者整除的数的两倍。

分析

核心观察

「只能被 $A$ ~A~ 与 $B$ ~B~ 之一整除」等价于落在「 $A$ ~A~ 的倍数」与「 $B$ ~B~ 的倍数」两个集合的对称差中。因此答案等于两个集合的大小之和减去两倍的集合交大小：既不被 $A$ ~A~ 整除也不被 $B$ ~B~ 整除的数不参与计算，而同时被两者整除的数一个都不该算，却在求和时被计了两次。

思路

在 $1 \sim N$ ~1 \sim N~ 中， $X$ ~X~ 的倍数恰有 $\lfloor N / X \rfloor$ ~\lfloor N / X \rfloor~ 个，所以两个集合的大小之和为

$\displaystyle \left\lfloor \frac{N}{A} \right\rfloor + \left\lfloor \frac{N}{B} \right\rfloor$

同时被 $A$ ~A~ 与 $B$ ~B~ 整除，等价于被二者的最小公倍数 $L$ ~L~ 整除，这样的数有 $\lfloor N / L \rfloor$ ~\lfloor N / L \rfloor~ 个。它们在上述求和里被各计了一次、共两次，而正确答案中它们不应出现，于是答案要减去两倍交集大小：

$\displaystyle \left\lfloor \frac{N}{A} \right\rfloor + \left\lfloor \frac{N}{B} \right\rfloor - 2 \left\lfloor \frac{N}{L} \right\rfloor$

其中最小公倍数取 $L = A \times B / \gcd(A, B)$ ~L = A \times B / \gcd(A, B)~，实用写法是先除后乘，即 $L = (A / \gcd(A, B)) \times B$ ~L = (A / \gcd(A, B)) \times B~。

这里必须用最小公倍数而不是 $A \times B$ ~A \times B~：当 $A$ ~A~ 与 $B$ ~B~ 不互质时 $A \times B$ ~A \times B~ 严格大于 $L$ ~L~，此时 $\lfloor N / (A \times B) \rfloor$ ~\lfloor N / (A \times B) \rfloor~ 会偏小，减得不够。例如 $N = 20$ ~N = 20~、 $A = 4$ ~A = 4~、 $B = 6$ ~B = 6~ 时正确结果是 $6$ ~6~，而用 $A \times B = 24$ ~A \times B = 24~ 会得到 $8$ ~8~。

朴素做法是从 $1$ ~1~ 枚举到 $N$ ~N~ 逐一判断，时间为 $O(N)$ ~O(N)~。本题 $N \leq 100$ ~N \leq 100~ 时两种做法都能通过，但公式法只需一次最大公约数计算，可以承受远大于 $100$ ~100~ 的 $N$ ~N~。

具体示例

样例 $1$ ~1~ 中 $N = 6$ ~N = 6~、 $A = 2$ ~A = 2~、 $B = 3$ ~B = 3~，两者互质，故 $L = 6$ ~L = 6~。

部分	计算	结果
$2$ ~2~ 的倍数	$\lfloor 6 / 2 \rfloor$ ~\lfloor 6 / 2 \rfloor~	$3$ ~3~（即 $2, 4, 6$ ~2, 4, 6~）
$3$ ~3~ 的倍数	$\lfloor 6 / 3 \rfloor$ ~\lfloor 6 / 3 \rfloor~	$2$ ~2~（即 $3, 6$ ~3, 6~）
同时是两个数的倍数	$\lfloor 6 / 6 \rfloor$ ~\lfloor 6 / 6 \rfloor~	$1$ ~1~（即 $6$ ~6~）

答案为 $3 + 2 - 2 \times 1 = 3$ ~3 + 2 - 2 \times 1 = 3~，对应 $2, 3, 4$ ~2, 3, 4~ 三个数：其中 $6$ ~6~ 被两个集合各计一次后恰好抵消，而 $1$ ~1~ 与 $5$ ~5~ 不属于任何集合，与样例一致。

样例 $3$ ~3~ 中 $N = 100$ ~N = 100~、 $A = 1$ ~A = 1~、 $B = 2$ ~B = 2~， $L = 2$ ~L = 2~，答案为 $100 + 50 - 2 \times 50 = 50$ ~100 + 50 - 2 \times 50 = 50~。

算法步骤

读入 N、A、B。
令 g 为 A 与 B 的最大公约数，令 L 为 A / g * B（先除后乘），即二者的最小公倍数。
令 ans 为 N 整除 A 的商与 N 整除 B 的商之和，再减去 N 整除 L 的商的两倍。
输出 ans。

复杂度分析

时间： $O(\log \min(A, B))$ ~O(\log \min(A, B))~，由求最大公约数的欧几里得算法决定，其余运算均为 $O(1)$ ~O(1)~。
空间： $O(1)$ ~O(1)~。

实现注意事项

交集是「同时被 $A$ ~A~ 与 $B$ ~B~ 整除」的数的个数，即最小公倍数的倍数个数，不能用 $A \times B$ ~A \times B~ 代替最小公倍数。
同时在两个集合中的数要减两倍，只减一倍会把这些数误算成「只能被之一整除」。
计算最小公倍数时先除后乘（a / std::gcd(a, b) * b），避免中间乘积溢出。
输入固定为三行三个正整数，按顺序读入即可，无需额外处理分隔符。
答案恒非负；本题范围 $N \leq 100$ ~N \leq 100~ 时 int 已足够，C++ 版本仍用 long long 以便范围扩大后直接复用。

源代码

#include <iostream>
#include <numeric>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long n = 0, a = 0, b = 0;
    std::cin >> n >> a >> b;

    const long long g = std::gcd(a, b);
    const long long l = a / g * b;  // 先除后乘，避免中间结果溢出

    // 被 A 或 B 整除的个数，减去同时被两者整除的个数（每个数被计了两次）
    std::cout << n / a + n / b - 2 * (n / l) << '\n';
    return 0;
}

import sys
from math import gcd


def main():
    n, a, b = map(int, sys.stdin.buffer.read().split())
    l = a // gcd(a, b) * b
    print(n // a + n // b - 2 * (n // l))


if __name__ == "__main__":
    main()

目前没有评论。