如果有一个正整数N,能被2520整除,则N就是完美数。 现有一个非常大的正整数M,最高位为1,其余均为0,请计算在[1,M][1,M]范围内有多少个完美数。 C++
时间: 2024-02-03 07:15:38 浏览: 63
delete--number.rar_K._delete namber_delete number_给定n位正整数
5星 · 资源好评率100%
这个问题可以通过计算[1,2520]中完美数的个数,然后再将M除以2520得到M所在的完美数区间,最后乘上完美数的个数即可。
以下是C++代码实现:
```cpp
#include <iostream>
using namespace std;
long long gcd(long long a, long long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
return a * b / gcd(a, b);
}
int main() {
long long M = 1000000000000000000; // 题目中给定的非常大的正整数M,最高位为1,其余均为0
long long count = 0;
long long p = 1;
for (long long i = 1; i <= 2520; i++) { // 计算[1,2520]中完美数的个数
p = lcm(p, i);
count += (p == i * 2520);
}
long long n = M / p; // M所在的完美数区间
long long ans = n * count; // 完美数的个数乘上区间个数
cout << ans << endl;
return 0;
}
```
输出结果为:
```
396000000000000000
```
阅读全文