整除：最大公约数和最小公倍数

数论►算法 , , , , 评论

0x13 最大公因数与最小公倍数

0x13.1 约数

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

唯一分解定理，任何一个大于 1 11 的数都可以被分解成有限个质数乘积的形式

N=∏i=1mpiCiN = \prod_{i=1}^{m}p_i^{C_i}

其中$ p_1 < p_2 < ··· < p_m为质数，为质数，C_i$为正整数

N 的正约数个数为：

(c1+1)×(c2+1)×⋯(cm+1)=∏i=1m(ci+1)(c1+1)\times (c_2+1)\times \cdots (c_m+1)=\prod_{i=1}^{m}(c_i+1)

NMN^M的正约数个数为：
$ (M\times {c_1}+1)\times (M\times {c_2}+1)\times \cdots (M\times {c_m}+1)=\prod_{i=1}^{m}(M\times {c_i}+1)$

N 的所有正约数和为：

$ (1+p_1+p_1^2+\cdots +p_1{c_1})\times\cdots\times(1+p_m+p_m2+\cdots +p_m{c_m})=\prod_{i=1}{m}(\sum_{j=0}{c_i}(p_i)j)$

随机数据下，约数个数的期望是O(ln⁡ n)O(\ln\ n)

  • 试除法 - 求 n的正约数集合

显然约数总是成对出现（除了完全平方数，只有一个$ \sqrt{n}$ ），所以只需要枚举到n\sqrt{n} 即可。

1
2
3
4
5
6
7
for(int i=1;i*i<=n;i++)
        if(n%i==0)
        {
            diver.emplace_back(i);
            if(n/i!=i)
            diver.emplace_back(n/i);
        }

a useful conclusion:

推论：一个整数 n 的约数个数上界为 2n2\sqrt{n}

  • 倍数法 - 求 1 ∼ n 1\sim n1∼n 中每个数的正约数集合

按照埃氏筛的形式枚举倍数，时间复杂度为O(n+n2+n3+⋯+nn)≈n×log⁡n=O(nlog⁡n)O(n+\cfrac n 2+\cfrac n 3+\cdots+\cfrac n n)≈n\times \log n=O(n\log n)

时间复杂度为O(nlog⁡n)O(n\log n)

可以求出求 1∼n1\sim n中每个数的正约数集合，但并不能求出具体某个数的因子是谁，常用于一些于因子有关的计算，如计算 ∑i=1n∑d∣nd\sum_{i=1}^{n}\sum_{d \mid n}d 或是$ \sum_{i=1}^{n}\sum_{d \mid n}f(d) $ ，可以使用倍数法在O(nlog⁡n)O(n\log n)的复杂度下计算。

1
2
3
4
5
6
7
8
9
10
11
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        for(int j = 1 ;j * i <= n; ++ j){
            factor[i * j].push_back(j);
        }
    }

    return 0;
}

推论：1∼n1\sim n中每个数的约数的总和大概为nlog⁡nn \log n。

0x13.2 最大公约数

两个数 a 和 b 的最大公约数$ \tt (Greatest Common Divisor) $是指同时整除 a和 b 的最大因数，记为 gcd⁡(a,b)\gcd(a, b)。

一个约定俗成的定理：任何非零整数和零的最大公约数为它本身。

有如下基本性质：

性质13.2.1：$ \gcd(a,b)=\gcd(b,a)$

性质13.2.2： gcd⁡(a,b)=gcd⁡(a−b,b)(a≥b)\gcd(a,b)=\gcd(a-b,b)\quad(a ≥b)

性质13.2.3：gcd⁡(a,b)=gcd⁡(a mod b,b)\gcd(a,b)=\gcd(a\bmod b,b)

性质13.2.4：gcd⁡(a,b,c)=gcd⁡(gcd⁡(a,b),c)\gcd(a,b,c)=\gcd(\gcd(a,b),c)

性质13.2.5：gcd⁡(ka,kb)=k gcd⁡(a,b)\gcd(ka,kb)=k\ \gcd(a,b)

性质13.2.6：gcd⁡(k,ab)=1  ⟺  gcd⁡(k,a)=1 && gcd⁡(k,b)=1\gcd(k,ab)=1 \iff \gcd(k,a)=1\ \&\&\ \gcd(k,b)=1

特别地，如果 a , b 的gcd⁡(a,b)=1\gcd(a,b)=1，则称这两个数互质（互素）。

  • 辗转相除法（又称欧几里德算法）

理论基础：
$ \forall a,b\in\N,b\neq 0,\gcd(a,b)=\gcd(b,a\ \mathrm{mod}\ b)$

时间复杂度 $ O(\log n)$

最坏情况：斐波那契数列相邻的两项，因为斐波那契数列相邻的两项一定互质。欧几里德算法由于存在大量的取模运算，对于大整数耗时较大。

  • Code

  • int gcd(int a, int b){
 return b == 0 ? a : gcd(b, a % b);
}
<!--code2-->

提前用位运算交换，很方便

0x13.3 最小公倍数

两个数 a和 b的最小公倍数 (LeatestCommonMultiple)\tt (Leatest Common Multiple)是指同时被 a 和 b 整除的最小倍数，记为 lcm(a,b)\text{lcm}(a, b)。特殊的，当a 和 b 互素时， lcm(a,b)=ab\text{lcm}(a, b) = ab。

性质13.3.1：∀a,b∈N,gcd⁡(a,b)×lcm(a,b)=a×b\forall a, b \in N,\gcd(a, b) \times \text{lcm}(a, b) = a \times b

可以使用 gcd ⁡ , lcm 的定义证明 性质13.3.1 ，证明略。

1
2
3
int lcm(int a,int b){
    return a / gcd(a,b) * b;//先除后乘，以免溢出64位整数
}

重要性质：gcd 与 lcm 的指数最值表示法
由唯一分解定理得，若

n=p1α1×p2α2×p3α3×⋯×pkαkn=p_1^{α_1}\times p_2^{α_2}\times p_3^{α_3}\times \cdots\times p_k^{α_k}

m=p1β1×p2β2×p3β3×⋯×pkβkm=p_1^{β_1}\times p_2^{β_2}\times p_3^{β_3}\times \cdots\times p_k^{β_k}

​则

n×m=p1α1+β1×p2α2+β2×p3α3+β3×⋯×pkαk+βkn\times m=p_1^{α_1+β_1}\times p_2^{α_2+β_2}\times p_3^{α_3+β_3}\times \cdots\times p_k^{α_k+β_k}

gcd⁡(n,m)=p1min{α1,β1}×p2min{α1,β1}×⋯×pkmin{αk,βk}\gcd(n,m)=p_1^{min\{α_1,β_1\}}\times p_2^{min\{α_1,β_1\}}\times \cdots\times p_k^{min\{α_k,β_k\}}

lcm(n,m)=p1max{α1,β1}×p2max{α1,β1}×⋯×pkmax{αk,βk}\text{lcm}(n,m)=p_1^{max\{α_1,β_1\}}\times p_2^{max\{α_1,β_1\}}\times \cdots\times p_k^{max\{α_k,β_k\}}

0x13.4 GCD 与 LCM 的一些性质与定理

性质13.4.1：fibnfib_n表示斐波那契数列的第n项

gcd⁡(fibn,fibm)=fibgcd⁡(n,m)\gcd\left(fib_{n},fib_{m}\right)=fib_{\gcd(n,m)}

性质13.4.2：

gcd⁡(am−1,an−1)=agcd⁡(n,m)−1 (a>1,n>0,m>0)\gcd(a^m−1,a^n−1)=a^{\gcd(n,m)}−1\ (a>1,n>0,m>0)

性质13.4.3：

gcd⁡(am−bm,an−bn)=agcd⁡(m,n)−bgcd⁡(m,n) (gcd(a,b)=1)\gcd(a^m−b^m,a^n−b^n)=a^{\gcd(m,n)}−b^{\gcd(m,n)}\quad \ (gcd(a,b)=1)

性质13.4.4：

gcd⁡(a,b)=1,gcd⁡(am,bn)=1\gcd(a,b)=1,\gcd(a^m,b^n)=1

性质13.4.5：

(a+b)∣ab⟹gcd⁡(a,b)≠1(a+b)\mid ab\Longrightarrow \gcd(a,b)\neq 1

a,b不互质，因为互质就提不出来公因子了。

性质13.4.6： 设G=gcd⁡(Cn1,Cn2,...Cnn−1)G=\gcd(C_n^1,C_n^2,...C_n^{n-1})

n 为素数，G = n
n 非素且有一个素因子 p ，G = p
n 有多个素因子，G = 1
性质13.4.7：

(n+1)lcm(Cn0,Cn1,⋯ ,Cnn)=lcm(1,2,⋯ ,n+1)(n+1)\text{lcm}(C_n^0,C_n^1,\cdots ,C_n^n)=\text{lcm}(1,2,\cdots ,n+1)

性质13.4.8：
∑i=1ngcd⁡(i,n)=∑d∣ndφ(nd)\displaystyle\sum^n_{i=1}\gcd(i,n)=\sum_{d|n}d\varphi(\frac{n}{d})
性质13.4.8：

在 FibonaccFibonacc 数列中求相邻两项的 ⁡ gcd⁡\gcd时，辗转相减次数等于辗转相除次数。

0x13.5 补充知识： FibonaccFibonacc 数列及其推论

基本性质定理：

\begin{align} fib_n&= \\&0 \quad(n=0); \\&1 \quad(n=1); \\&fib_{n-1}+fib_{n-2} \quad(n=2); \end{align}

推导结论：
性质13.5.1： ∑i=1nfi=fn+2−1\sum_{i=1}^{n}{f_{i}}=f_{n+2}-1

性质13.5.2：∑i=1nf2i−1=f2n\sum_{i=1}^{n}{f_{2i-1}}=f_{2n}

性质13.5.3： ∑i=1nf2i=f2n+1−1\sum_{i=1}^{n}{f_{2i}}=f_{2n+1}-1

性质13.5.4：∑i=1n(fn)2=fnfn+1\sum_{i=1}^{n}{(f_{n})^2}=f_{n}f_{n+1}

性质13.5.5：fn+m=fn−1fm−1+fnfmf_{n+m}=f_{n-1}f_{m-1}+f_{n}f_{m}

性质13.5.6： (fn)2=(−1)(n−1)+fn−1fn+1(f_{n})^2=(-1)^{(n-1)}+f_{n-1}f_{n+1}

性质13.5.7：f2n−1=(fn)2−(fn−2)2f_{2n-1}=(f_{n})^2-(f_{n-2})^2

性质13.5.8：fn=fn+2+fn−23f_{n}=\cfrac{f_{n+2}+f_{n-2}}{3}

性质13.5.9： $\frac{f_{i}}{f_{i-1}} \approx \dfrac{\sqrt{5}-1}{2} \approx 0.618 $

性质13.5.10：fn=(1+52)n−(1−52)n5f_{n}=\cfrac{\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}}{\sqrt{5}}

​

Modified GCD

题目描述

Well, here is another math class task. In mathematics, GCD is the greatest common divisor, and it’s an easy task to calculate the GCD between two positive integers.

A common divisor for two positive numbers is a number which both numbers are divisible by.

But your teacher wants to give you a harder task, in this task you have to find the greatest common divisor $ d $ between two integers $ a $ and $ b $ that is in a given range from $ low $ to $ high $ (inclusive), i.e. $ low<=d<=high $ . It is possible that there is no common divisor in the given range.

You will be given the two integers $ a $ and $ b $ , then $ n $ queries. Each query is a range from $ low $ to $ high $ and you have to answer each query.

输入格式

The first line contains two integers $ a $ and $ b $ , the two integers as described above ( $ 1<=a,b<=10^{9} $ ). The second line contains one integer $ n $ , the number of queries ( $ 1<=n<=10^{4} $ ). Then $ n $ lines follow, each line contains one query consisting of two integers, $ low $ and $ high $ ( $ 1<=low<=high<=10^{9} $ ).

输出格式

Print $ n $ lines. The $ i $ -th of them should contain the result of the $ i $ -th query in the input. If there is no common divisor in the given range for any query, you should print -1 as a result for this query.

样例输入 #1
1
2
3
4
5
9 27
3
1 5
10 11
9 11
样例输出 #1
1
2
3
3
-1
9

解决这题首先要来看一个命题：

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
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
vector<int> diver;
int gcd(int a,int b)
{
    if(a<b){a^=b;b^=a;a^=b;}//交换a，b的值交换后恒有a>b
    if(!b)return a;
    if(!(a&1)&&!(b&1))return 2*gcd(a>>1,b>>1);
    else if(!(a&1))return gcd(a>>1,b);
    else if(!(b&1))return gcd(a,b>>1);
    else return gcd(a-b,b);
}
signed main()
{
    int a,b;
    cin>>a>>b;
    int grst_com_div=gcd(a,b);
    //cout<<grst_com_div<<endl;
    int n;
    for(int i=1;i*i<=grst_com_div;i++)
        if(grst_com_div%i==0)
        {
            diver.emplace_back(i);
            if(grst_com_div/i!=i)
            diver.emplace_back(grst_com_div/i);
        }//求出最大公约数的所有因子
    sort(diver.begin(),diver.end()) ; 
    //对所有因子排序
    //for(auto j:diver)cout<<j<<" ";
    cin>>n;
    while(n--)//回答n次询问
    {
        int l,r,ans=-1;
        cin>>l>>r;
        int i=0,j=diver.size()-1;
        while(i<=j)//二分查找解决确定区间问题
        {
            int mid=j+(i-j)/2;
            if(diver[mid]>=l && diver[mid]<=r)
            {
                ans=diver[mid];
                i = mid + 1;
            }
            else if(diver[mid]<l)
                i=mid+1;
            else j=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

XQC-1368我见青山多妩媚 料青山见我应如是

Harbin Institute of Technology, Shenzhen 计算机科学与技术 本科在读