`算法知识` 最大公约数GCD

算法 {约数,最大公约数GCD}

约数

定義

對於正整數a, 他的約數集合為: 正整數集合裡 滿足a % ? == 0的數的集合;
. 比如1的約數集合為{1}, 2的約數集合為{1,2}, 3的約數集合為{1,3};

性質

#1是任何正整數的約數#;

算法

求一個數的所有约数之和 (O(1))

代碼

divisor_sum = 1;
for( [prime,power] : `a的質因數分解`)){
	divisor_sum *= (1 + prime + `prime^2` + ... + `prime^power`);
}
1
2
3
4

求一個數的约数的个数 (O(1))

性质

#int a; a的约数个数 的最大值为1536#
当a等于1745944200/ 2113511400时, 他的约数个数为1536; 此时a的质因数分解为2^3 * 3^3 * 5^2 * 7 * 11 * 13 * 17 * (19/23);

代码

divisor_count = 1;
for( [prime,power] : `a的質因數分解`)){
	divisor_count *= (power + 1);
}
1
2
3
4

求一個數的所有约数

预处理 $O(K)+O(?)$

+ $O(K)$ where $K$ is the Divisor-Count(at most $<1600$ if the number is int)
+ $O(?)$ means the process of Prime-Factorization for the number;
+ If you wanna all divisors are sorted, add sort( divisors, divisors + divisor_count); in @Location_0;

//{ All_Divisors-Declaration
class All_Divisors{ //< @Singleton
public:
    using Type_ = @Unfinished; //< @Unfinished
    //< @Name(Type_) is the type of the target-number (i.e., the number represented by @Var(prime_factorization)), and is also the type of the Prime-Factors;
    //-- definition ends
    const Type_ * Divisors;
    //-- variable ends
    All_Divisors( const pair< Type_, int> *);
    int Get_divisorCount() const;
    void Initialize( int);
private:
    static constexpr int divisor_MaxCount_ = @Unfinished ; //< @Unfinished is `1600` if $(@Name = int));
    //-- definition ends
    const pair< Type_, int> * prime_factorization;
    Type_ divisors[ divisor_MaxCount_];
    int divisor_count;
    int range;
    //-- variable ends
    void dfs( int, Type_);
};
//} All_Divisors-Declaration

//{ All_Divisors-Implementation
All_Divisors::All_Divisors( const pair< Type_, int> * _primeFactorization)
        :
        prime_factorization( _primeFactorization){
    //{ Singleton-Check
    static bool __singleton_flag = true;
    ASSERT_( __singleton_flag);
     __singleton_flag = false;
    //} Singleton-Check
    Divisors = divisors;
}
int All_Divisors::Get_divisorCount() const{ return divisor_count;}
void All_Divisors::Initialize( int _range){
//< + @Name(_range): the Array-Length of @Var(prime_factorization)
    range = _range;
    //--
    divisor_count = 0;
    dfs( 0, 1);
    //>< @Location_0
}
void All_Divisors::dfs( int _ind, Type_ _num){
    if( _ind >= range){
        ASSERT_( divisor_count < divisor_MaxCount_);
        divisors[ divisor_count ++] = _num;
        return;
    }
    //--
    dfs( _ind + 1, _num);
    for( int p = 1; p <= prime_factorization[ _ind].second; ++p){
        _num *= prime_factorization[ _ind].first;
        dfs( _ind + 1, _num);
    }
}
//} All_Divisors-Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

一次性 $O(\sqrt{a})$

{ // 求一個數`a`的所有約數;
    auto a = ?;
    ASSERT_( a >= 1);
    using T_ = decltype(a);
    vector divisors; // `a`的所有約數 (不是遞增的 但所有元素一定互不相同);
    divisors.push_back( 1);
    if( a != 1){
        divisors.push_back( a);
    }
    for( int i = 2; i <= a / i; ++i){
        if( a % i == 0){
            divisors.push_back( i);
            if( i != a/i){
                divisors.push_back( a/i);
            }
        }
    }
} // 求一個數`a`的所有約數;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

笔记

Property-1
$x$ 的约数个数

$A=p_1^{a_1}\ast p_2^{a_2}\ast ...$, then the number of divisors of $A$ equals $(1+a_1)\ast (1+a_2)\ast ...$;

Proof:
. For any divisor $a$ of $A$, every Prime-Factor of $a$ must be also a Prime-Factor of $A$;
. Therefore, for every item $p_i^{a_i}$, there are $a_1+1$ choices: $p_i^0,p_i^1,p_i^2,...$;

@Delimter;

Property-2
$a\in int$ 的最大约数个数

The Maximal-Divisor-Count in the range int $[1,2147483647]$ is $1536$;
. Two numbers $a=1745944200/2113511400$ attains this peak: $2^3\ast 3^3\ast 5^2\ast 7\ast 11\ast 13\ast 17\ast (19/23)$;

最大公约数GCD

定義

#最大公約數/Greatest Common Divisor/GCD#
若干個正整數$Ai$, 找到最大的$T>0$ 滿足: $\forall a\in Ai,a\%T=0$;
. 比如{4,6,6}的GCD為2;
. #等價定義#: 所有Ai的約數集合的交集 中的最大值, 為GCD;

性質

#從質因數分解角度去看GCD;#
令a = p1^k1 * p2^k2 * p3^k3 * ..., b = p1^kk1 * p2^kk2 * p3^kk3 * ..., c = p1^kkk1 * p2^kkk2 * p3^kkk3 * ...;
那麼 p1^min(k1,kk1,kkk1) * p2^min(k2,kk2,kkk2) * p3^min(k3,kk3,kkk3) * ... 就是a,b,c的GCD;

@DELI;

#GCD的除法#
已知GCD(a,b) == c; 對於c的任意的約數d, 則有GCD(a/d, b/d) == c/d;
. 證明: 可以藉助上一條性質, 令d = p1^K1 * p2^K2 * ..., 那麼因為k1/kk1/kkk1 >= K1, 整除除法 在質因數分解的角度 就是做指數的減法, 即c/d等於 讓c的各個指數減去K1,K2,..., 又因為min(k1-K1, kk1-K1, kkk1-K1) == min(k1,kk1,kkk1)-K1;

算法

兩個數的GCD

template< class _T> _T GCD( _T _a, _T _b){
    while( _a != 0){
        _a %= _b; swap( _a, _b);
    }
    return _b;
} // GCD
1
2
3
4
5
6

多個數的GCD

int ANS = 0;
for( auto i : 若干數){
	ANS = GCD( ANS, i);
}
1
2
3
4

求$N\times N$裡 GCD==質數的數對的個數

@LINK: (https://editor.csdn.net/md/?not_checkout=1&articleId=126848932)-(@LOC_1);

例题

https://editor.csdn.net/md/?not_checkout=1&articleId=130320865

筆記

对两数AB的GCD, (规定两者都是自然数, 且不同时为$0$)

假设AB的所有公约数集合是S, 做法是: 找到另外两个数CD, 其公约数集合也等于S;
… 公约数集合相同, 自然最大公约数也相同;

令A >= B, A = Ka * G, B = Kb * G (G为AB的GCD, Ka与Kb互质)

令C = A % B, 即: C = (Ka % Kb) * G

根据: 取模数, 可知: C与Kb一定互质, 但与Ka不一定互质;

即, (A, B的GCD)为G, 而(B, C的GCD)也为G;

故求(A, B)的GCD, 且A>=B, 等价于求(B, A%B)的GCD
因为要保证第一参数>=第二参数, 所以要写成(B, A%B), 而不是(A%B, B)

---

比如, 求(10, 6)的GCD

(10, 6) -> (6, 4) -> (4, 2) -> (2, 0)

每次取模, 相当于取半, 所以时间是Log2(N);
递归的终结是: 第二参数为0