如果有一个正整数N,能被2520整除,则N就是完美数。现有一个非常大的正整数M,最高位为1,其余均为0,请计算在[1,M]范围内有多少个完美数C++代码
时间: 2023-12-31 14:06:25 浏览: 46
这道题可以用数学方法解决。我们知道,2520可以被1~10的所有整数整除,因此,如果一个数N能被2520整除,那么它一定能被1~10的所有整数整除。所以,我们可以从1~10中选取若干个数,计算它们的最小公倍数,得到一个完美数。因此,我们只需要计算1~10的最小公倍数,然后枚举该最小公倍数的倍数即可。具体实现如下:
```cpp
#include <iostream>
using namespace std;
const long long M = 1000000000000000000LL; // 最大范围
long long gcd(long long a, long long b) { // 最大公约数
return b == 0 ? a : gcd(b, a % b);
}
long long lcm(long long a, long long b) { // 最小公倍数
return a * b / gcd(a, b);
}
int main() {
long long ans = 0, L = 1;
for (int i = 1; i <= 10; ++i) { // 计算最小公倍数
L = lcm(L, i);
}
while (L <= M) { // 枚举完美数
++ans;
L += L;
}
cout << ans << endl;
return 0;
}
```
这个程序的时间复杂度为O(logM),因此对于范围很大的M来说也是可以接受的。