如果有一个正整数N,能被2520整除,则N就是完美数。 现有一个非常大的正整数M,最高位为1,其余均为0,请计算在[1,M][1,M]范围内有多少个完美数。c++语言
时间: 2024-02-05 17:14:08 浏览: 16
题目中要求的是在区间 [1,M] 中有多少个完美数,我们可以按照下列步骤进行求解:
1. 由于 M 非常大,直接用循环枚举每个数肯定会超时,因此我们需要优化。
2. 首先,我们可以发现,2520 是一个非常重要的因子,因为它是 1~10 中所有数的最小公倍数,也就是说,任何一个完美数一定能被 2520 整除。因此,我们可以将循环的步长设为 2520,这样就可以大幅度减小循环次数。
3. 其次,我们可以预处理出 2520 的倍数中有哪些数是完美数,然后在循环中直接累加完美数的个数即可。
下面是代码实现:
```c++
#include <iostream>
using namespace std;
const int MAXN = 1e18;
const int LCM = 2520;
bool isPerfect[LCM];
int main() {
for (int i = 1; i <= LCM; i++) {
int tmp = i;
for (int j = 2; j <= 10; j++) {
while (tmp % j == 0) tmp /= j;
if (tmp == 1) {
isPerfect[i] = true;
break;
}
}
}
long long n, ans = 0;
cin >> n;
for (long long i = LCM; i <= n; i += LCM) {
ans += isPerfect[i % LCM];
}
cout << ans << endl;
return 0;
}
```
这里需要注意的是,由于数据范围非常大,因此需要使用 long long 类型来存储输入的整数和计算过程中的变量。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)