约数和定理

求约数和

给定一个数 \(n\) 如何求 \(n\) 的所有约数之和？

对于每个正整数 \(n\) 都可以分解成一些素数的乘积：

\(n = p_1^{k_1}p_2^{k_2} \cdots p_n^{k_n}\)

则任意一个约数都可以表示成：

\(n = p_1^{s_1}p_2^{s_2} \cdots p_n^{s_n}\)，其中 \(s_1 \leq k_1, s_2 \leq k_2, \cdots s_n \leq k_n\)

所以所有的约数和可以表示成：

\(s = (p_1 ^ 0 + p_1 ^ 1 + \cdots p_1 ^ {k_1}) \times (p_2 ^ 0 + p_2 ^ 1 + \cdots p_2 ^ {k_2}) \times \cdots \times (p_n ^ 0 + p_n ^ 1 + \cdots p_n ^ {k_n})\)

求一个数的约数之和代码参考：

代码比较杂：边记录素数的最高次方，边记录和

typedef long long LL;
const LL mod = LL (1e9 + 7);
unordered_map<LL, vector<LL>> ps;

LL add_ds(LL n)
{
    for (int i = 2; i <= n / i; i ++)
    {
        if (n % i == 0)
        {
            auto node = ps.find(i);
            if (node == ps.end())
            {
                ps.insert({i, {1, 1}});
                node = ps.find(i);
            }
            while (n % i == 0)
            {
                node->second[0] = node->second[0] * i % mod;
                node->second[1] = (node->second[1] + node->second[0]) % mod;
                n /= i;
            }
        }
    }
    if (n > 1) ps.insert({n, {n, 1 + n}});
    LL ans = 1;
    for (auto [x, y] : ps)
    {
        ans = ans * y[1] % mod;
    }
    return ans;
}

代码精简版：直接记录素数的个数

typedef long long LL;
const LL mod = LL (1e9 + 7);
unordered_map<LL, LL> pn;

LL add_ds(LL n)
{
    for (int i = 2; i <= n / i; i ++)
    {
        if (n % i == 0)
        {
            auto & t = pn[i];
            while (n % i == 0) t ++, n /= i;
        }
    }
    if (n > 1) pn[n] ++;
    LL ans = 1;
    for (auto [x, y] : pn)
    {
        LL a = 1, b = 1;
        while (y --) a = a * x % mod, b = (b + a) % mod;
        ans = ans * b % mod;
    }
    return ans;
}

871.约数之和

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

思路，和上面的差不多，也是统计所有的素因子。

边记录各素数的最高次的值，边累加代码参考

#include <bits/stdc++.h>

using namespace std;
int debuggersum = 0;

// 即使是不成熟的尝试，

typedef long long LL;
const LL mod = (1e9 + 7);
unordered_map<LL, vector<LL>> ps;

void add_ds(LL n)
{
    for (int i = 2; i <= n / i; i ++)
    {
        if (n % i == 0)
        {
            auto node = ps.find(i);
            if (node == ps.end())
            {
                ps.insert({i, {1, 1}});
                node = ps.find(i);
            }
            while (n % i == 0)
            {
                LL x = node->second[0] = node->second[0] * i % mod;
                node->second[1] = (node->second[1] + x) % mod;
                n /= i;
            }
        }
    }
    if (n > 1) 
    {
        auto node = ps.find(n);
        if (node == ps.end())
        {
            ps.insert({n, {1, 1}});
            node = ps.find(n);
        }
        LL x = node->second[0] = node->second[0] * n % mod;
        node->second[1] = (node->second[1] + x) % mod;
    }
}

void solve(void)
{
    int n; scanf ("%d", &n);
    while (n --)
    {
        int t; scanf ("%d", &t); add_ds(t);
    }
    LL ans = 1;
    for (auto [x, y] : ps)
        ans = ans * y[1] % mod;
    printf ("%lld\n", ans);
}

// 也胜于胎死腹中的策略。

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo << "start running ..." << endl; fo.close(); fi.close();
        for (long long i = 1; i <= 4e8 + 2e7; i++);
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}

直接记录素数个数代码参考

#include <bits/stdc++.h>

using namespace std;
int debuggersum = 0;

// 即使是不成熟的尝试，

typedef long long LL;
const LL mod = LL (1e9 + 7);
unordered_map<LL, LL> pn;

void add_ds(LL n)
{
    for (int i = 2; i <= n / i; i ++)
    {
        if (n % i == 0)
        {
            auto & t = pn[i];
            while (n % i == 0) t ++, n /= i;
        }
    }
    if (n > 1) pn[n] ++;
}

void solve(void)
{
    int n; scanf ("%d", &n);
    while (n --)
    {
        int t; scanf ("%d", &t); add_ds(t);
    }
    LL ans = 1;
    for (auto [x, y] : pn)
    {
        LL a = 1, b = 1;
        while (y --) a = a * x % mod, b = (b + a) % mod;
        ans = ans * b % mod;
    }
    printf ("%lld\n", ans);
}

// 也胜于胎死腹中的策略。

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo << "start running ..." << endl; fo.close(); fi.close();
        for (long long i = 1; i <= 4e8 + 2e7; i++);
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}