约数问题

试除法求约数

遍历范围是1~sqrt(x)，每次找到约数时，把自身和另一个同时放入
最后需要排序，但实际上消耗的时间不多，int最大值才有大约1500个约数

代码

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;
}

约数个数

如果 N = p1^c1 * p2^c2 * ... *pk^ck

约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)

约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

• 数学原理：
  • 一个整数能唯一展开成若干个质数乘积的形式$n = p_1^{c_1}\times p_2^{c_2} \times … \times p_k^{c_k}$
  • 整数相乘等价于对应质指数相加$n_1 \times n_2= (p_1^{a_1}\times p_2^{a_2} \times … \times p_k^{a_k}) \times (p_1^{b_1}\times p_2^{b_2} \times … \times p_k^{b_k})= p_1^{a_1+b_1}\times p_2^{a_2+b_2} \times … \times p_k^{a_k+b_k}$
• 例子：$12=2^2\times3^1$，$12$的约数有$1, 2, 3, 4, 6, 12$共$6$个，根据公式计算同样是$(2+1)\times(1+1)=6$个

代码

unordered_map<int, int> primes;     // 用哈希表保存质数的指数

// 质数分解
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 elem : primes) res = res * (elem.second + 1);

约数之和

$sum=\prod_{i=1}^k{\sum_{j=0}^{c_i}{p_{i}^{j}}}=(p_1^0 + p_1^1 + … + p_1^{c_1})\times…\times(p_k^0 + p_k^1 + … + p_k^{c_k})$

• 例子：$12=2^2\times3^1$，$12$的约数有$1, 2, 3, 4, 6, 12$，约数之和为$28$，根据公式计算同样是$(2^0+2^1+2^2)\times(3^0+3^1)=28$个
• $p^0+p^1+p^2+…+p^n=…((1 \times p + 1)\times p + 1)…$，其中里边迭代n次。因此可直接用结果进行迭代计算，而不用一个变量存储中间值

代码

LL res = 1;
for (auto elem : primes) {
    int p = elem.first, a = elem.second;
    LL sum = 1;
    while(a--) sum = sum * p + 1;
    res *= sum;
}

最大公约数-欧几里得算法

原理

gcd(a,b)=gcd(b,a mod b)

``gcd(a,0)=a`

代码

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}