约数个数和约数之和算法总结

2024-01-07 17:32:34

知识概览

约数个数

由算数基本定理

N = p_1^{\alpha_{1}}p_2^{\alpha_{2}} \cdots p_k^{\alpha_{k}}

可得对于N的任何一个约数d，有

d = p_1^{\beta_{1}}p_2^{\beta_{2}} \cdots p_k^{\beta_{k}}, 0\leqslant \beta_{i}\leqslant \alpha_{i}

因为N的每一个约数和\beta_{1}~\beta_{k}的一种选法是一一对应的，根据乘法原理可得，

一个数的约数个数为

(\alpha_{1} + 1)(\alpha_{2} + 1) \cdots (\alpha_{k} + 1)

约数之和

一个数的约数之和公式为

(p_1^{0} + p_1^{1} + \cdots + p_1^{\alpha_1})\cdots (p_k^{0} + p_k^{1} + \cdots + p_k^{\alpha_k})

多项式乘积的每一项为

p_1^{\beta_{1}}p_2^{\beta_{2}} \cdots p_k^{\beta_{k}}

正好对应的是一个数的每一个约数。

例题展示

约数个数

题目链接

活动 - AcWing 系统讲解常用算法与数据结构，给出相应代码模板，并会布置、讲解相应的基础算法题目。icon-default.png?t=N7T8https://www.acwing.com/problem/content/872/

代码
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    
    unordered_map<int, int> primes;
    while (n--)
    {
        int x;
        cin >> x;
        
        for (int i = 2; i <= x / i; i++)
            while (x % i == 0)
            {
                x /= i;
                primes[i]++;
            }
            
        if (x > 1) primes[x]++;
    }
    
    LL res = 1;
    for (auto prime : primes) res = res * (prime.second + 1) % mod;
    
    cout << res << endl;
    
    return 0;
}

约数之和

题目链接

活动 - AcWing 系统讲解常用算法与数据结构，给出相应代码模板，并会布置、讲解相应的基础算法题目。icon-default.png?t=N7T8https://www.acwing.com/problem/content/873/

代码
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    
    unordered_map<int, int> primes;
    while (n--)
    {
        int x;
        cin >> x;
        
        for (int i = 2; i <= x / i; i++)
            while (x % i == 0)
            {
                x /= i;
                primes[i]++;
            }
            
        if (x > 1) primes[x]++;
    }
    
    LL res = 1;
    for (auto prime : primes)
    {
        int p = prime.first, a = prime.second;
        LL t = 1;
        while (a--) t = (t * p + 1) % mod;
        res = res * t % mod;
    }
    
    cout << res << endl;
    
    return 0;
}

参考资料

  1. AcWing算法基础课

文章来源:https://blog.csdn.net/u012181348/article/details/135438918
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。