约数总结

试除法求约数

方法1-试除所有数

算法原理

假设p是x的一个约数，那么x/p一定也是它的约数，所以只需枚举2 到 $\sqrt[2]{n}$的约数，并且可以直接通过运算获得 $\sqrt[2]{n}$ 之后对应的那个约数 时间复杂度$O(\sqrt{n})$

代码实现

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; ++ i)
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}
int main()
{
    int n;
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;
        auto res = get_divisors(x);
        for (int t : res) cout << t << ' ';
        cout << endl;
    }
    return 0;
}

方法2:质因数分解 + dfs

算法原理 此做法的原理和计算所有约数的和有些类似，属于排列组合问题。 对于每个质数，我们选择其一种指数情况，所有质数相乘在一些就属于一个约数，暴搜所有情况即可(暴搜具有可行性的原因是int范围内具有约数最多的数具有1600个约数，情况很少，暴搜是可以实现的)

算法流程

1. 首先使用线性筛获取所需范围的质数
2. 对数据进行质因数分解
3. dfs获取所有约数

代码实现

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int primes[N], cnt;
bool st[N];
PII primes_factor[N];
int divisors[N];
int cntf, cntd;

void init(int n)
{
    for (int i = 2; i <= n; ++ i)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] * i <= n; ++ j)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
void dfs(int u, int p)
{
    if (u == cntf)
    {
        divisors[cntd ++] = p;
        return ;
    }
    for (int i = 0; i <= primes_factor[u].second; ++ i)
    {
        dfs(u + 1, p);
        p *= primes_factor[u].first;
    }
}
void get_divisors(int n)
{
    cntf = 0;
    for (int i = 0; i < cnt; ++ i)
    {
        int p = primes[i];
        if (n % p == 0)
        {
            int s = 0;
            while (n % p == 0)
            {
                ++ s;
                n /= p;
            }
            primes_factor[cntf ++] = {p, s};
        }
    }
    if (n > 1) primes_factor[cntf ++] = {n, 1};
    
    cntd = 0;
    dfs(0, 1);
}
int main()
{
    init(50000);
    
    int n;
    cin >> n;
    
    while (n --)
    {
        int x;
        cin >> x;
        
        get_divisors(x);
        
        sort(divisors, divisors + cntd);
        for (int i = 0; i < cntd; ++ i) cout << divisors[i] << ' ';
        cout << endl;
    }
    return 0;
}

计算约数个数

int范围内具有最多约数的数拥有$1600$个约数

算法原理

根据唯一分解定理，任意数n可表示为 $ n = p_1^{\alpha_1} * p_2^{\alpha_2} * ... * p_n^{\alpha_n} $， 选择一定量的 $ P_1 , P_2, ... ,P_n $ 相乘获得n的约数，总的选择方案为$(\alpha_1 + 1) * (\alpha_2 + 1) * ... * (\alpha_n + 1)$，其中加1表示指数可以为0

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int MOD = 1e9 + 7;

unordered_map<int, int> primes;

inline void get_divisors(int x)
{
    for (int i = 2; i <= x / i; ++ i)
        while (x % i == 0)
        {
            x /= i;
            ++ primes[i];
        }
    if (x > 1) ++ primes[x];
}
int main()
{
    int x;
    cin >> x;
    get_divisors(x);
    
    long long res = 1;
    for (auto prime : primes) res = res * (prime.second + 1) % MOD;
    cout << res << endl;
    return 0;
}

计算所有约数的和

算法思想

$(p_1^{\alpha_1} + p_1^{\alpha_2} + ... + p_2^{\alpha_n}) * (p_2^{\alpha_1} + p_2^{\alpha_2} + ... + p_2^{\alpha_n}) * ... * (p_n^{\alpha_1} + p_n^{\alpha_2} + ... + p_n^{\alpha_n})$，展开之后一共是$(\alpha_1 + 1) * (\alpha_2 + 1) * ... * (\alpha_n + 1)$项，每一项的形式均为$ p_1^{k_1} * p_2^{k_2} * ... * p_n^{k_n} $，即每一项都是一个约数，所有约数加在一起即为答案

代码实现

代码中计算 $ p_1^{0} + p_1^{1} + ... + p_2^{\alpha_1}$ 时候采用了非常巧妙的做法。可以概括为当我们计算 $\sum_{i = 0}^{\alpha}p^i$ 这种求和时，可以采用下面的代码

int t = 1; // 最终结果
while(a --) // a表示p的最大指数
    t = t * p + 1;

#include <iostream>
#include <unordered_map>

using namespace std;

int n;
const int MOD = 1e9 + 7;

unordered_map<int, int> primes;

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

计算倍数个数

1到n中p的倍数(或者说能被p整除)的数有 $\lfloor \frac{n}{p} \rfloor$ 个

原理很简单，1到n中p的倍数为 $1p, 2p, 3p, ... kp$，当$kp$恰好等于n时，总个数为 $\frac {n}{p}$；当$kp<n$ 且 $(k+1)*p>n$ 时，总个数为 $\lfloor \frac{n}{p} \rfloor$。将两种情况结合在一起就是$\lfloor \frac{n}{p} \rfloor$

1到n中既是$p_1$的倍数，又是$p_2$的倍数有 $\lfloor \frac{n}{p_1 \ * \ p_2} \rfloor$ 个($p_1$ 和 $p_2$保证互质)

首先我们假设$p_1$和$p_2$是两个不相等的质数且m既是$p_1$的倍数(为了后续公式的简便，这里假设就是1倍的关系)，又是$p_2$的倍数(同前)，根据唯一分解定理，m的质因数分解式中一定是$p_1 \ * \ p_2 \ * \ ...$的形式，所以m一定可以整除 $p_1 \ * \ p_2$，所以也就是求1到n中$p_1 \ * \ p_2$倍数的个数。 上述公式中，对于$p_1$ 和 $p_2$的要求是保证互质即可，并没有限制必须均为质数，原因在于即使两个数中存在合数，比如4和7，但是由于两个数是互质的，所以两者质因数分解的结果中一定不包含相同的质因子，所以和上面两个数均是质数的情况一样，如果某数m是4和7的倍数，那么它一定是4*7的倍数。 综上所述，上述公式是正确的。