J. Divisibility - 题解
比赛与标签
比赛: Experimental Educational Round: VolBIT Formulas Blitz 标签: math, number theory 难度: *1100
Petya的奖金小目标喵~
主人你好呀~！(ฅ'ω'ฅ) 这道题目其实是一个非常可爱的数学小谜题哦！
事情是这样的：IT City公司有一个超棒的奖励机制！每当一款游戏的销量，能够被从2到10所有整数（也就是2, 3, 4, 5, 6, 7, 8, 9, 10）整除的时候，所有参与开发的员工都能拿到一笔小奖金~
现在，可爱的游戏设计师Petya预测，他参与开发的新游戏在第一个月能卖出 n 份。他想知道，在这个月里，他总共能拿到多少次奖金呢？
我们的任务就是，给定一个数字 n，计算出从1到 n 之间，有多少个数字能够同时被2到10这九个数字整除。
输入: 一个整数 n (1 ≤ n ≤ 1018)。 输出: 一个整数，表示能拿到奖金的次数。
找到那个神奇的数字！喵~
一看到“同时被好几个数整除”，聪明的猫娘我呀，DNA就动了！这不就是我们最熟悉的 最小公倍数 (Least Common Multiple, LCM) 的应用场景嘛，的说！
如果一个数字 X 能够同时被 2, 3, 4, 5, 6, 7, 8, 9, 10 整除，那么 X 一定是它们的公倍数。为了找到所有这样的 X，我们只需要找到它们的最小公倍数 L。任何满足条件的 X 都必然是 L 的倍数，呐。
所以，我们的解题思路分为两步：
- 计算出
LCM(2, 3, 4, 5, 6, 7, 8, 9, 10)。 - 计算在
[1, n]的范围内，有多少个这个LCM的倍数。
Step 1: 计算最小公倍数
我们来分解一下这些数字的质因数吧！
- 2 = 2
- 3 = 3
- 4 = 2²
- 5 = 5
- 6 = 2 × 3
- 7 = 7
- 8 = 2³
- 9 = 3²
- 10 = 2 × 5
计算最小公倍数的方法是，找出所有出现过的质因数，并取它们最高次幂的乘积。
- 对于质因数 2，最高次幂是来自 8 的 2³。
- 对于质因数 3，最高次幂是来自 9 的 3²。
- 对于质因数 5，最高次幂是来自 5 (或10) 的 5¹。
- 对于质因数 7，最高次幂是来自 7 的 7¹。
所以，LCM = 2³ × 3² × 5¹ × 7¹ = 8 × 9 × 5 × 7。 我们来算一下：8 × 9 = 72，5 × 7 = 35。 最后，72 × 35 = 2520。
哇哦！我们找到了这个神奇的数字——2520！也就是说，一个数能被2到10整除，当且仅当它能被2520整除！
Step 2: 统计倍数个数
现在问题就变得超级简单啦！我们只需要计算在1到 n 之间，有多少个2520的倍数。
这就像是问：“10个苹果分给3个小朋友，每人能分到几个？”一样，直接用除法就可以啦！ 在 [1, n] 中，k 的倍数个数就是 n / k（向下取整）。
所以，答案就是 n / 2520！因为 n 是整数类型，在C++里做除法会自动向下取整，正好是我们想要的结果，喵~
代码时间到！Let's Code! 喵~
#include <iostream>
using namespace std;
int main() {
// 题目给出的n最大可以到10^18，普通的int类型会溢出哦
// 所以必须使用 long long 来存储，这样才能装下这么大的数字，喵~
long long n;
// 从标准输入读取预测的销量 n
cin >> n;
// 我们已经计算出，一个数要被2到10所有数整除，
// 就必须是它们的最小公倍数 2520 的倍数。
// 所以问题就转化成了求 [1, n] 中有多少个2520的倍数。
// 这可以通过整数除法 n / 2520 直接得到结果！
cout << n / 2520 << endl;
return 0;
}效率怎么样呢？
时间复杂度: O(1) 的说 我们的程序只进行了一次读入、一次除法和一次输出。这些操作的执行时间都是固定的，和输入
n的大小无关，所以是常数时间复杂度。超级快的！( •̀ ω •́ )✧空间复杂度: O(1) 的说 我们只用了一个
long long类型的变量n来存储输入。无论n多大，我们占用的内存空间都是固定的。所以是常数空间复杂度，非常节省内存呐！
猫娘的小课堂时间~
这道题虽然简单，但背后的小知识点很关键哦，记在小本本上吧！
核心知识点：最小公倍数 (LCM) 这是数论的基础知识。当题目要求一个数同时被多个数整除时，一定要立刻想到是它们的最小公倍数的倍数。这是解决这类问题的金钥匙！
解题技巧：问题转化 我们把一个看起来有点复杂的“被2到10都整除”的问题，成功转化为了一个非常简单的“被2520整除”的问题。这种化繁为简的能力，在算法竞赛中非常重要哦！
编程注意点：数据范围 看到
10^18这么大的数字，就要立刻警觉起来！int类型在大多数平台上只能表示到大约2 × 10^9，是远远不够的。这时候就要毫不犹豫地使用long long(C++) 或者其他64位整型，不然就会因为数据溢出而得到错误答案，那就太可惜了喵。
希望这篇题解能帮到你哦！继续加油，享受思考和编程的乐趣吧，喵~ ( ´ ▽ ` )ﾉ