文章

119

粉丝

68

获赞

92

访问

20.2k

头像
约数的个数 题解:约数定理
P1152 清华大学上机题
发布于2025年2月7日 11:58
阅读数 109

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;  // 输入为 0 时退出
        while (n--) {
            long long x;
            cin >> x;  // 读取需要计算因数个数的数
            int ans = 1;  // 初始化结果为 1
            for (int i = 2; i * i <= x; i++) {  // 分解质因数
                int r = 0;
                while (x % i == 0) {
                    x /= i;
                    r++;
                }
                if (r > 0) ans *= r + 1;  // 更新因数个数
            }
            if (x > 1) ans *= 2;  // 处理剩余的质因数
            cout << ans << endl;  // 输出结果
        }
    }
    return 0;
}

参考了大佬的解法,学习了约数定理,以及对任意一个数进行质因数分解的办法,以及分解层次的解法,这样的解效率很好。

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发