K. Indivisibility - 题解

比赛与标签

比赛: Experimental Educational Round: VolBIT Formulas Blitz 标签: math, number theory 难度: *1500

喵喵，题目要我们做什么呀？

主人，这道题目的意思是这样的呐：在一个月内，有一款新游戏的总销量预计为 n。游戏公司有一个奇特的奖励规则，每当累计销量数不能被 2 到 10 之间的任何一个整数整除时，开发者们就能获得一笔小奖金。

我们要扮演一个聪明的游戏设计师 Petya，预测一下从 1 到 n 这些销量数字中，有多少个是满足奖励条件的。也就是说，我们要找出在 [1, n] 这个区间里，有多少个数不能被 2, 3, 4, 5, 6, 7, 8, 9, 10 中的任何一个数整除，的说。

输入: 一个整数 n (1 ≤ n ≤ 10^18)，代表预测的总销量。输出: 一个整数，代表能获得奖金的次数。

容斥原理，一学就会的魔法喵~

一开始看到要判断不能被 2 到 10 这么多数字整除，可能会有点头大，对吧？但是我们来仔细分析一下这个条件，喵~

"不能被 2 到 10 之间的任何数整除"，我们来看看这些数：2, 3, 4, 5, 6, 7, 8, 9, 10。这里面有些是“多余”的哦！

如果一个数能被 4 整除，那它肯定能被 2 整除。
如果一个数能被 6 整除，那它肯定能被 2 和 3 整除。
如果一个数能被 8 整除，那它肯定能被 2 整除。
如果一个数能被 9 整除，那它肯定能被 3 整除。
如果一个数能被 10 整除，那它肯定能被 2 和 5 整除。

所以，一个数只要能被 {2, 3, 5, 7} 这四个质数中的任何一个整除，它就不可能满足奖励条件了！反过来说，一个数如果不能被 {2, 3, 5, 7} 中的任何一个整除，那它也一定不能被 {4, 6, 8, 9, 10} 整除。

于是，问题就华丽丽地变身啦！我们只需要找出 [1, n] 中，有多少个数不能被 2、3、5、7 中任何一个整除。

直接计算“不能”有点困难，但我们可以换个思路呐！我们可以先算出有多少个数是“坏”的（即至少能被 2、3、5、7 中的一个整除），然后用总数 n 减去这个“坏”数的数量，剩下的不就是“好”数的数量了嘛？

计算“至少能被一个数整除”的数量，就要用到我们强大的数学魔法——容斥原理（Inclusion-Exclusion Principle）啦！

想象一下四个圈圈，分别代表能被 2、3、5、7 整除的数的集合。我们想求这些圈圈并集的大小。

加上单个的：先把所有圈圈的大小都加起来。 （能被2整除的）+（能被3整除的）+（能被5整除的）+（能被7整除的）n/2 + n/3 + n/5 + n/7
减去重复的：这么加会把两个圈圈重叠的部分多算了一次，所以要减掉。 减去（能被2和3整除的） -> 减去（能被6整除的）减去（能被2和5整除的） -> 减去（能被10整除的） ... 以此类推，减去所有两两组合的。
加回多减的：但是！减去两两组合的时候，又把三个圈圈重叠的部分多减了一次，所以要再加回来。 加上（能被2、3、5整除的） -> 加上（能被30整除的） ... 以此类推，加上所有三个一组的。
再减去多加的：最后，四个圈圈重叠的部分又被多算了一次，要再减掉。 减去（能被2、3、5、7整除的） -> 减去（能被210整除的）

这样一加一减，我们就精确地算出了所有“坏”数的数量 total。最后用 n - total 就是我们想要的答案啦，喵~！

让代码动起来吧，喵！

下面就是把我们刚才的魔法思路变成代码的样子，很简单吧！

cpp

#include <iostream>
using namespace std;

int main() {
    // n 的范围很大，最大到 10^18，所以必须用 long long 来存储，不然会溢出的说！
    long long n;
    cin >> n;

    // total 用来计算 [1, n] 中至少能被 2, 3, 5, 7 中一个整除的数的总数
    long long total = 0;

    // 第一步 (Inclusion)：加上所有能被单个质数整除的数的数量
    // n / k 可以直接得到 [1, n] 中 k 的倍数的个数
    total += n / 2;
    total += n / 3;
    total += n / 5;
    total += n / 7;

    // 第二步 (Exclusion)：减去所有能被两个质数乘积整除的数的数量
    // 因为它们在第一步中被重复计算了
    total -= n / (2 * 3); // 6
    total -= n / (2 * 5); // 10
    total -= n / (2 * 7); // 14
    total -= n / (3 * 5); // 15
    total -= n / (3 * 7); // 21
    total -= n / (5 * 7); // 35

    // 第三步 (Inclusion)：加回所有能被三个质数乘积整除的数的数量
    // 因为它们在第一步加了3次，在第二步又被减了3次，等于没算，所以要加回来
    total += n / (2 * 3 * 5); // 30
    total += n / (2 * 3 * 7); // 42
    total += n / (2 * 5 * 7); // 70
    total += n / (3 * 5 * 7); // 105

    // 第四步 (Exclusion)：减去所有能被四个质数乘积整除的数的数量
    // 经过前三步，它们被多算了一次，所以要减掉
    total -= n / (2 * 3 * 5 * 7); // 210

    // n 减去所有“不符合条件”的数的数量，剩下的就是“符合条件”的啦！
    cout << n - total << endl;

    return 0;
}

复杂度分析

时间复杂度: O(1) 的说。因为无论输入的 n 有多大，我们的程序都只执行固定次数的加、减、乘、除运算。计算量是恒定的，不会随着 n 的增长而增长，超级快！
空间复杂度: O(1) 的说。我们只用了几个 long long 类型的变量来存储输入和中间结果，占用的内存空间也是一个固定的常量，非常节省空间呐！

小猫娘的知识宝库~

这道题真是太有趣啦，它教会了我们几件重要的事情：

问题转化是关键：有时候，一个看起来很复杂的问题（不能被2到10整除），可以通过分析其内在逻辑，转化为一个更简单、更经典的问题（不能被质数2,3,5,7整除）。这是解题的第一步，也是最重要的一步！
容斥原理大法好：当遇到“至少满足一个条件”的计数问题时，一定要想起容斥原理这个强大的工具！它的“加加减减”思想可以精确地处理各种集合重叠问题。
注意数据范围：看到 10^18 这样的输入范围，就要立刻警惕起来，普通的 int 是绝对不够用的，必须使用 long long 来防止数据溢出，这可是竞赛中的基本功哦！

希望这篇题解能帮助主人更好地理解这道题目！以后遇到类似的问题，也要像这样，先冷静分析，再运用合适的数学工具，一定能迎刃而解的喵~！加油哦！(๑•̀ㅂ•́)و✧

K. Indivisibility - 题解 ​

比赛与标签 ​

喵喵，题目要我们做什么呀？ ​

容斥原理，一学就会的魔法喵~ ​

让代码动起来吧，喵！ ​

复杂度分析 ​

小猫娘的知识宝库~ ​