如果有一个正整数N，能被2520整除，则N就是完美数。 现有一个非常大的正整数M，最高位为1，其余均为0，请计算在[1,M]范围内有多少个完美数。 输入：输入一个正整数M 输出：完美数的个数 样例输入1:10000 样例输出1:3 样例输入2:1000000 样例输出2:396 C++代码实现

这道题可以通过计算约数个数来判断一个数是否能被2520整除。因为2520的所有因数都是1~9的倍数，所以如果一个数的因数个数可以被9整除且这个数本身是9的倍数，则这个数能被2520整除。具体实现如下：

#include <iostream>
using namespace std;

const int MAXN = 1e6;

int main() {
    int m;
    cin >> m;

    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        if (i % 9 == 0 && i % 2520 == 0) { // 判断是否能被2520整除
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;
}

时间复杂度为$O(M)$，可以通过本题。

相关问题

如果有一个正整数N，能被2520整除，则N就是完美数。现有一个非常大的正整数M，最高位为1，其余均为0，请计算在[1,M][1,M]范围内有多少个完美数。输入一个正整数M完美数的个数

根据题意，可以得知完美数是能被2520整除的正整数。而2520可以分解成$2^3 \times 3^2 \times 5 \times 7$，因此一个数能够被2520整除，必须包含$2^3$，$3^2$，$5$，$7$这四个质因数。那么我们只需要统计1到M中包含这四个质因数的数的个数即可。

设$f_1(n)$表示1到n中包含质因数2的数的个数，$f_2(n)$表示1到n中包含质因数3的数的个数，$f_3(n)$表示1到n中包含质因数5的数的个数，$f_4(n)$表示1到n中包含质因数7的数的个数。那么1到M中包含这四个质因数的数的个数就是$f_1(M)f_2(M)f_3(M)f_4(M)$。

对于$f_1(n)$，可以发现，1到n中每隔2个数就会出现一个包含质因数2的数，每隔4个数就会出现一个包含2的平方的数，每隔8个数就会出现一个包含2的立方的数，以此类推。因此$f_1(n)=\lfloor\frac{n}{2}\rfloor+\lfloor\frac{n}{4}\rfloor+\lfloor\frac{n}{8}\rfloor+\cdots$。

同理，$f_2(n),f_3(n),f_4(n)$也可以用类似的方法计算。代码如下：

如果有一个正整数N，能被2520整除，则N就是完美数。 现有一个非常大的正整数M，最高位为1，其余均为0，请计算在[1,M][1,M]范围内有多少个完美数。 输入 输入一个正整数M 输出 完美数的个数

这道题需要先了解什么是“最小公倍数”和什么是“完美数”。

最小公倍数：两个数a、b的最小公倍数是能够同时被a和b整除的最小正整数。我们可以通过求两个数的最大公约数来计算它们的最小公倍数。

完美数：一个正整数n是完美数，当且仅当它等于除自身外的所有正因子之和。例如，6是完美数，因为6 = 1 + 2 + 3。

根据题意，我们需要找到在[1,M]范围内能够被2520整除的完美数的个数。由于2520是1~10中所有正整数的最小公倍数，因此我们只需要找到1~10中的完美数，然后再根据M的位数来计算出[1,M]范围内的完美数的个数。

1~10中的完美数有6个，分别是6、28、496、8128、33550336、8589869056。

假设M的位数为n，则[1,M]范围内的最小数为1，最大数为$10^n-1$。因此，[1,M]范围内的完美数个数为：

$\lfloor\frac{10^n-1}{2520}\rfloor\times6$

其中，$\lfloor x \rfloor$ 表示不大于x的最大整数。

下面是Python代码实现：

import math

m = int(input())
n = len(str(m))

perfect_nums = [6, 28, 496, 8128, 33550336, 8589869056]
count = math.floor((10**n-1)/2520) * 6

print(count)