2020年编程奥林匹克竞赛：第二轮 (SACO 2020 Round 2)

竞赛规则摘要：

• 答题时间：120 分钟（2 小时）。
• 题目数量：共 4 题，每题 100 分。
• 提交限制：每位选手最多提交 30 次。
• 评分标准：每个子任务独立计分，取该子任务所有提交中的最高分。
• 合规性：禁止访问外部网站，程序需通过查重检测。

题目 1：特殊数字计数 (Count Special)

题目描述

给定两个正整数 $A$ 和 $B$。如果一个正整数能被 $A$ 或 $B$（或同时被两者）整除，我们就称这个数为“特殊数字”。 请编写一个程序，计算在给定的整数 $N$ 之下（不包含 $N$ 本身），共有多少个特殊数字。

输入格式

输入包含 3 个以空格分隔的整数：$A, B, N$。

• $1 \le A, B \le \min(N, 10^6)$
• $1 \le N \le 10^{18}$

输出格式

输出一个整数，代表小于 $N$ 的特殊数字的总数。

计分与子任务

• 子任务 1 (0 分)：样例测试。
• 子任务 2 (80 分)：$1 \le N \le 10^6$。
• 子任务 3 (20 分)：$1 \le N \le 10^{18}$（注意：需使用 64 位整数类型）。

算法思路：容斥原理 (Inclusion-Exclusion Principle)

计算小于 $N$ 且能被 $A$ 或 $B$ 整除的数字数量，可以使用经典的容斥原理：

1. 计算小于 $N$ 且能被 $A$ 整除的个数：$countA = \lfloor (N-1) / A \rfloor$
2. 计算小于 $N$ 且能被 $B$ 整除的个数：$countB = \lfloor (N-1) / B \rfloor$
3. 注意重复：同时能被 $A$ 和 $B$ 整除的数（即能被 $A$ 和 $B$ 的最小公倍数整除的数）被计算了两次。
4. 最小公倍数计算公式：$LCM(A, B) = (A \times B) / GCD(A, B)$
5. 最终结果：$Ans = countA + countB - \lfloor$ $(N-1) / LCM(A, B) \rfloor$