最大公约数

思路

用gcd(a,b)表示a、b的最大公约数，有：gcd(a,b) = gcd(b,a % b)。

代码

1
2
3
int gcd(int a,int b) {
    return b == 0? a : gcd(b,a % b);
}

最小公倍数

gcd(a,b) * a * b

公约数

思路

a,b的公约数一定可以整除gcd(a,b)，gcd(a,b)的约数一定是a,b的公约数

可以用算术基本定理简单证明

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int a,b,q;
int x,y;

vector<int> divs;

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

void get_div(int d) {
    for(int i = 1; i * i <= d; ++ i) 
        if(d % i == 0) {
            divs.push_back(i);
            if(i / d != i) divs.push_back(d / i);
        }
    sort(divs.begin(),divs.end());
}