AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

约数&约数个数&约数之和&最大公约数

作者: 作者的头像   echomingzhu ,  2019-10-20 12:29:11 ,  所有人可见 ,  阅读 1277


12


8

1.核心思想

  1. 质数判断:试除法
  2. 约数个数:任何一个数 n ,一定能够表示成 n = a0^p0 * a1^p1 * a2^p2 ... ak^pk, 其中 a0,a1,a2...ak都是质数,那么数 n的所有约数个数 T = (1+p0)(1+p1)(1+p2)...(1+pk)
  3. 约数之和: 任何一个数 n ,一定能够表示成 n = a0^p0 * a1^p1 * a2^p2 ... ak^pk, 其中 a0,a1,a2...ak都是质数,那么数 n的所有约数之和
S = (a0^0 + a0^1 + a0^2 + ... a0^p0) * (a1^0 + a1^1 + a1^2 + ... a1^p1) * (a2^0 + a2^1 + a2^2 + ... a2^p2)...(ak^0 + ak^1 + ak^2 + ... ak^pk)
  1. 最大公约数:
gcd(a, b) = gcd(b, a mod b)

2. 代码模板

1. 约数
for(int i = 1; i <= a / i; i++){
    if(a % i == 0){
        int b = a / i;
        if(b == i){
            printf("%d ", i);
        } else {
            printf("%d %d", i, b);
        }
    }
}

2. 约数个数
LL ans = 1;
unordered_map<int,int> hash;
cin >> x;
for(int i = 2;i <= x/i; ++i){
    while(x % i == 0){
        x /= i;
        hash[i] ++;
    }
}
if(x > 1) hash[x] ++;

for(auto i : hash) ans = ans*(i.second + 1) % mod;
cout << ans;

3. 约数之和
LL ans = 1;
unordered_map<int,int> hash;
cin >> x;
for(int i = 2;i <= x/i; ++i){
    while(x % i == 0){
        x /= i;
        hash[i] ++;
    }
}
if(x > 1) hash[x] ++;

for(auto i : hash){
    LL temp = 0;
    LL subSum = 0;
    for(int j = 0; j <= i.second; j++){
        if(j == 0){
            temp = 1;
            subSum = 1;
        } else {
            temp = temp * i.first % mod;
            subSum = subSum + temp % mod;
        }
    }
    ans = ans * (subSum % mod) % mod;
}

4. 最大公约数
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

3 评论


用户头像
T-SHLoRk   2019-10-21 17:23         踩      回复

写的很棒 通俗易懂


用户头像
秦淮岸灯火阑珊   2019-10-20 19:09         踩      回复

棒!

用户头像
echomingzhu   2019-10-20 21:18         踩      回复

tks


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息