能整数该数的数就是约数

试除法求约数

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

约数个数

  • 任何一个合数都可以表示成质数相乘。所以,一个数的约数也一定是它的某种质数组合。
  • 比如说,x 是由质数 $p12*p23$ 那么它的约数(2 + 1) * (3 + 1), $p10p2$ 必然能整除 x,其他的类似。
  • 所以我们只需要知道一个数是由哪几个质数的幂次组成,就能求出约数的个数。
  • 求约数的公式:N = (a1 + 1)(a2 + 1) ... (an + 1)。 ai 表示对应质数的幂次。

约数之和

  • 我们知道任何一个数都可以表示为质数的幂次组合。
  • 公式:$sum=(p10+p11+...+p1c)...(pk0+pk1+...+pkc)$

最大公因数

欧几里得定理或辗转相除法

  • (a, b) = (b, a%b) 定理:a,b的最大共约数等于,b,a%b 的最大共约数。
  • 证明:
    • 右边 = 左边
    • a%b=a-floor(a/b)b=a-cb (floor(a/b) 看成是一个 c)
    • 设 d 为(a,b)最大公约数,则 d | a, d | b <=> d | a-cb (a-cb = a mod b)

模板

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