求约数个数、约数之和

求约数最简单的方法(

试除法

):

如果 i 是 n 的约数,那么 n / i 也是 n 的约数

代码

    for(int i = 1; i <= x / i; i++)
    {
        if(x % i == 0)
        {
            res.push_back(i);
            if(i != n / i) res.push_back(x / i); //这里注意,如果i = n / i不用再存
        }
    }

求约数的另一种方法(

算数基本定理

):

任意一个数 N 都可以唯一分解成以下的形式


N = p1^α1 * p2^α2 * p3^α3 * … * pi^αi

αi的取值为

[0,αi]


任意一个 N 的约数 d 同样可以分解为以上的形式


d = p1^β1 * p2^β2 * p3^β3 … * pi^βi

βi的取值为

[0,αi]

所以约数的个数就为:

(α1 + 1) * (α2 + 1) * (α3 + 1) * …

举个例子 270 = 2*3*3*3*5 = 2^1 + 3^3 + 5^1

那么270的约数个数就为:(1 + 1) * (3 + 1) * (1 + 1) = 16

这16个约数分别为:

1 2 3 5 6 9 10 15 18 27 30 45 54 90 135 270

求约数之和


由上面求约数的方法,不难得约数之和的公式为:


(p1^0 + p1^1 + … + p1^α1) * … * (pi^0 + pi^1 + … + pi^αi)

求(pi^0 + pi^1 + … + pi^αi)的技巧


直接用等比数列公式求和会爆

这样写的话就不会出问题

t = 1
while(α--) //α是指数,p是底数
{
	t = t * p + 1;
}

约数个数


给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 10^9+7 取模。

输入格式


第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai。

输出格式


输出一个整数，表示所给正整数的乘积的约数个数，答案需对 10^9+7 取模。

数据范围


1≤n≤100,

1≤ai≤2×10^9

输入样例：

3
2
6
8

输出样例：

12

代码

#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;

unordered_map<int,int> primes;
int n;
LL res = 1;

const int mod = 1e9+7;

int main()
{
    cin >> n;
    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]++;
    }
    for(auto t : primes) res = res * (t.second + 1) % mod;
    cout << res << endl;
    return 0;
}

约数之和


给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 10^9+7 取模。

输入格式


第一行包含整数 n。

输出格式


输出一个整数，表示所给正整数的乘积的约数之和，答案需对 10^9+7 取模。

数据范围


1≤n≤100,

1≤ai≤2×10^9

输入样例：

3
2
6
8

输出样例：

252

代码

#include <iostream>
#include <unordered_map>

using namespace std;

const int mod = 1e9+7;

typedef long long LL;

int n;
LL res = 1;
unordered_map<int,int> primes;

int main()
{
    cin >> n;
    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]++;
    }
    for(auto p : primes)
    {
        LL a = p.first,b = p.second; // a是底数,b是指数
        LL t = 1;
        while(b--) t = (t * a + 1) % mod;
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}