题目
容斥原理
思路
这道题主要考察容斥原理
容斥原理是组合数学中一个重要的计数方法。它用于计算多个集合的交集和并集的大小。
假设有两个集合 A A A 和 B B B，它们的大小分别为 ∣ A ∣ |A| ∣A∣ 和 ∣ B ∣ |B| ∣B∣。那么它们的交集大小为 ∣ A ∩ B ∣ |A∩B| ∣A∩B∣，并集大小为 ∣ A ∪ B ∣ |A∪B| ∣A∪B∣。容斥原理告诉我们：
∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ |A∪B| = |A| + |B| - |A∩B| ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣
换句话说，如果我们想要计算两个集合的并集大小，我们需要把它们的大小加起来，但是此时会把它们的交集计算两次，因此需要减去交集的大小。
这个原理可以推广到多个集合的情况。假设有 n n n 个集合 A 1 , A 2 , . . . , A n A_1, A_2, ..., A_n A1,A2,...,An，它们的交集大小为 ∣ A 1 ∩ A 2 ∩ . . . ∩ A n ∣ |A_1∩A_2∩...∩A_n| ∣A1∩A2∩...∩An∣，并集大小为 ∣ A 1 ∪ A 2 ∪ . . . ∪ A n ∣ |A_1∪A_2∪...∪A_n| ∣A1∪A2∪...∪An∣。那么容斥原理告诉我们：
∣ A 1 ∪ A 2 ∪ . . . ∪ A n ∣ = Σ ∣ A i ∣ − Σ ∣ A i ∩ A j ∣ + Σ ∣ A i ∩ A j ∩ A k ∣ − . . . + ( − 1 ) n + 1 ∣ A 1 ∩ A 2 ∩ . . . ∩ A n ∣ |A_1∪A_2∪...∪A_n| = Σ|A_i| - Σ|A_i∩A_j| + Σ|A_i∩A_j∩A_k| - ... + (-1)^{n+1}|A_1∩A_2∩...∩A_n| ∣A1∪A2∪...∪An∣=Σ∣Ai∣−Σ∣Ai∩Aj∣+Σ∣Ai∩Aj∩Ak∣−...+(−1)n+1∣A1∩A2∩...∩An∣
其中 Σ Σ Σ 表示求和， i < j < k < . . . i<j<k<... i<j<k<...表示所有可能的组合， ( − 1 ) n + 1 (-1)^{n+1} (−1)n+1是一个符号，当 n n n 为奇数时为 − 1 -1 −1，当 n n n 为偶数时为 1 1 1。
那么这道题怎么使用容斥原理呢？
题目要求不是 2 , 5 , 11 , 13 2,5,11,13 2,5,11,13 的倍数的个数，那么我们就先求出 2 , 5 , 11 , 13 2,5,11,13 2,5,11,13 的倍数的个数，然后再用 n n n 减去这个个数即可。怎么求个数呢？
就是先求 2 2 2 的倍数的个数，再求 5 5 5 的倍数的个数，… 再求 2 × 5 × 11 × 13 2\times 5\times 11\times 13 2×5×11×13 的倍数的个数， 然后将这些个数用容斥原理连起来即可，具体见代码。
代码
#include <stdio.h>
typedef long long LL;
LL solve(LL n) {
LL a = n / 2;
LL b = n / 5;
LL c = n / 11;
LL d = n / 13;
LL e = n / (2 * 5);
LL f = n / (2 * 11);
LL g = n / (2 * 13);
LL h = n / (5 * 11);
LL i = n / (5 * 13);
LL j = n / (11 * 13);
LL k = n / (2 * 5 * 11);
LL l = n / (2 * 5 * 13);
LL m = n / (2 * 11 * 13);
LL o = n / (5 * 11 * 13);
LL p = n / (2 * 5 * 11 * 13);
// 除了用 n 减的这部分，后面的部分就是容斥原理（将正负号变换一下）
return n - a - b - c - d + e + f + g + h + i + j - k - l - m - o + p;
}
int main(void) {
LL n = 0;
// 注意本题有多组输入，只读入一个是不行的
while(~scanf("%lld", &n)){
printf("%lld\n", solve(n));
}
return 0;
}