约数

约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

试除法求约数

#include <bits/stdc++.h>
using namespace std;

vector<int> get(int n)
{
    vector<int> res;
    for (int i = 1; i <= n / i; i ++ ){
        if (n % i == 0){
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main()
{
    int n;
    cin >> n;
    while (n -- ){
        int x;
        cin >> x;
        auto res = get(x);
        for (auto it : res) cout << it << ' ';
        cout << endl;
    }

    return 0;
}

约数个数定理

对于一个大于1正整数n可以分解质因数

则n的正约数的个数就是

其中a1、a2、a3…ak是p1、p2、p3，…pk的指数。（摘自百度百科）

此处用map做一个映射，键表示约数，值表示指数，然后遵照约束个数定理计算即可。

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;

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

    long long res = 1;
    for (auto it : primes) res = res * (it.second + 1) % mod;

    cout << res << endl;

    return 0;
}

约数和定理

对于一个大于1正整数n可以分解质因数：n=p1^a1 * p2^a2 * p3^a3 * … * pk^ak

则由约数个数定理可知n的正约数有(a₁+1)(a₂+1)(a₃+1)…(ak+1)个，

那么n的(a₁+1)(a₂+1)(a₃+1)…(ak+1)个正约数的和为

f(n)=(p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）

对于每一项pn，我们可以表示为p1^a1 + p1^a1-1 …. pi^1 + 1的形式，那么对每一项，我们都让它乘a1再加1即可（秦九韶算法）

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;

    unordered_map<int, int> primes;

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

    long long res = 1;
    for (auto it : primes){
        long long a = it.first, b = it.second;

        long long t = 1;
        while (b -- ){
            t = (t * a + 1) % mod;
        }
        res = res * t % mod;
    }

    cout << res << endl;

    return 0;
}

最大公约数GCD

计算方法：欧几里得法（辗转相除法）

递归写法：

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int main()
{
    int tt;
    cin >> tt;
    while (tt -- ){
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }

    return 0;
}

拓展 最小公倍数LCM

其实最小公倍数可以由最大公因数得：lcm(a, b) = a * b / gcd(a, b)

拓展欧几里得算法 EXGCD

裴蜀定理

对于任意的整数a，b，都一定存在整数x，y使ax+by=d，d为gcd(a,b)的倍数。

拓展欧几里得算法是在gcd递归的过程中加上x与y的迭代

设ax1+by1=gcd(a,b), bx2+(a%b)y2=gcd(b,a%b);
由gcd(a,b)=gcd(b,a%b),可得:
ax1+by1=bx2+(a%b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2
=ay2+bx2-(a/b) * by2;
即:ax1+by1=ay2 + b(x2-(a/b) * y2)
根据恒等定理,对应项相等，得:x1=y2; y1=x2-(a/b)*y2;
这样我们就得到了:x1，y1的值基于x2，y2，所以我们可以通过递归求解。

#include <bits/stdc++.h>
using namespace std;

void exgcd(int a, int b, int &x, int &y)
{
    if (!b){
        x = 1, y = 0;
    }
    else{
        exgcd(b, a % b, y, x), y -= a / b * x; // xy互换
    }
}

int main()
{
    int tt;
    cin >> tt;
    
    while (tt -- ){
        int a, b;
        cin >> a >> b;
        int x, y;
        exgcd(a, b, x, y);
        
        cout << x << ' ' << y << endl;
    }
    
    return 0;
}