约数相关算法

试除法求一个数的所有约数

题目：httpss://www.acwing.com/problem/content/871/

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

using namespace std;

vector<int> get_divisor(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_divisor(x);
        for (auto t : res) cout << t << " ";
        cout << endl;
    }
}

约数的个数

任意一个数能够表示为下面的式子：

举例:

求$2 * 6 * 8 = 96$三个数乘积的约数个数

$2:2^1$

$6: 2^1*3^1$

$8:2^3$

也就是: $a = p_1\text{\textasciicircum}\left(\alpha_1\right) = 2^5, b = p_2\text{\textasciicircum}\left(\alpha_2\right) = 3^1$

$a$有$5+1$个约数，$b$有$1+1$个约数

则约数个数为$6*2=12$，

符合乘法定理, 通俗易懂的讲就是 相当于96的约数是在它的最小质因数里面随便选几个组合而成

题目： httpss://www.acwing.com/problem/content/872/

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

using namespace std;
typedef long long LL;
const int mod = 1e9 + 7, N = 110;


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]++;
    }
    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;
    
    cout << res << endl;
    return 0;
}

约数之和

还是用上一个例子证明

我们得到这个式子之后，可以继续拆分

$a = p_1\text{\textasciicircum}\left(\alpha_1\right) = 2^5, b = p_2\text{\textasciicircum}\left(\alpha_2\right) = 3^1$

$a$的约数的和就是$(2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5)$ ,

$b$的约数的和为 $(3^0 + 3^1)$

显而易得：

因此$96$的约数和为 $(2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5)*(3^0 + 3^1)$

还有最繁琐的办法就是一个一个算上面图的里面数字乘积的和

题目：httpss://www.acwing.com/problem/content/873/

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

using namespace std;
typedef long long LL;
unordered_map<int, int> primes;

const int mod = 1e9 + 7;
int main()
{
    int n ; 
    cin >> n;
    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] ++;
    }
    
    LL res = 1;
    for (auto prime: primes)
    {
        int p = prime.first, a = prime.second;
        LL t = 1;
        while(a --) t = (t * p + 1) %mod;
        res = res *t %mod;
    }
    
    cout << res <<endl;

}

最大公约数

如果 $d$ $|$ $a$ , $d$ $|$ $b$

那么 $d$ $|$ $ax+by$

证明：$(a, b)$ $= (b, a$ $mod$ $b)$ 成立

因为 $a$ $mod$ $b$ $= a$ $-$ $\lfloor \dfrac{a}{b} \rfloor$ $*b$

举例：$5$ mod $2 = 5 - 2 * 2 = 1$

然后我们可以写成下面的形式：

$a$ $mod$ $b$ $= a$ $-$ $c*b$

然后带入到欧几里得算法的算式：

$(a, b)$ $= (b, a-c*b)$

因为左边 $d$ $|$ $a$ , $d$ $|$ $b$ ，也就是存在一个公约数$d$能被$a$，和$b$整除

右边只需要证明 $d$ $|$ $a - c*b$即可。因为右边 $d$ $|$ $b$ ， 所以可以将$c*b$消掉。

$d$ $|$ $a - c*b + c*b$ $=$ $d$ $|$ $a$,

所以左边和右边的公约数相等

题目：httpss://www.acwing.com/problem/content/874/

#include <iostream>
#include <algorithm>
using namespace std;

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

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