约数

约数是什么

若(a=b*k)且(k)为整数,则称(b)是(a)的约数.

最大公约数

定义

两个整数的共有约数中最大的一个就是它们的最大公约数.(a)和(b)的最大公约数用(gcd(a,b))表示.

算法

辗转相除法

又称欧几里得算法.
设(a=k*b+r),(r equiv a pmod{b}),(lmid a)且(lmid b).
( herefore r=a-k*b),(frac{r}{l}=frac{a}{l}-frac{k*b}{l})
又(ecause lmid a,lmid b)
( herefore frac{r}{l})为整数
( herefore lmid r)
( herefore {a,b})的公约数与(b,a\%b)的公约数完全一致
( herefore gcd(a,b)=gcd(b,a\%b))
用这种方法不断递归,直到(a=b)时,返回(a)即可.

int gcd(long long a,long long b) {
    if(a==b) return a;
    if(a<b) swap(a,b);
    return gcd(b,a%b);
}

时间复杂度为(O(log {b})).

二进制算法

该算法一般用于高精度.

1. 当(2mid a)且(2mid b)时,(gcd(a,b)=2*gcd(frac{a}{2},frac{b}{2})).
2. 当(2mid a)但(2 mid b)时,(gcd(a,b)=gcd(frac{a}{2},b)).
3. 当(2 mid a)且(2 mid b)时,(gcd(a,b)=gcd(frac{a-b}{2},b)).

以下为高精度代码(压位).

#include<bits/stdc++.h>
#define w 18 //压位位数,2-18
using namespace std;
const long long len=pow(10,w);
struct data{
    long long num[10005],size;
}a,b;
void read(data &x) {
    char c[10005];
    int re[10005];
    memset(re,0,sizeof(re));
    cin>>c;
    for(int i=0; i<strlen(c); i++) {
        re[strlen(c)-i]=c[i]-'0';
    }
    x.size=0;
    for(int i=1;i<=strlen(c)/w+1;i++) {
		for(int j=0;j<w;j++) {
			x.num[i]*=10;
			x.num[i]+=re[w*i-j];
		}
        if(x.num[i]) x.size=i;
    }
}
void write(data x) {
    for(int i=x.size; i>0; i--) {
        if(i==x.size) {
            cout<<x.num[i];
            continue;
        }
        cout<<setw(w)<<setfill('0')<<x.num[i];
    }
}
void div2(data &x) {
    for(int i=x.size;i>0;i--) {
        if(x.num[i]&1) x.num[i-1]+=len;
        x.num[i]>>=1;
        if(!x.num[x.size]) x.size--;
    }
}
int div(data &x) {
    int cnt=0;
    while(!(x.num[1]&1)) div2(x),cnt++;
    return cnt;
}
void exc(data &x,data &y) {
    swap(x.size,y.size);
    for(int i=1;i<=max(x.size,y.size);i++) swap(x.num[i],y.num[i]);
}
bool change(data &x,data &y) {
    if(x.size>y.size) return false;
    if(x.size<y.size) {
        exc(x,y);
        return false;
    }
    for(int i=max(x.size,y.size);i>0;i--) {
        if(x.num[i]>y.num[i]) return false;
        if(x.num[i]<y.num[i]) {
            exc(x,y);
            return false;
        }
    }
    return true;
}
void time2(data &x) {
    for(int i=x.size;i>0;i--) {
        x.num[i]<<=1;
        if(x.num[i]>len-1) x.num[i]-=len,x.num[i+1]+=1;
    }
    int cnt=0;
    while(x.num[++cnt]) {
        if(x.num[cnt]>len-1) x.num[cnt]-=len,x.num[cnt+1]+=1;
    }
    if(x.num[x.size+1]) x.size++;
}
void time(data &x,int p) {
    for(int i=1;i<=p;i++) time2(x);
}
void reduce() {
    for(int i=1;i<=min(a.size,b.size);i++) {
        a.num[i]-=b.num[i];
        if(a.num[i]<0) a.num[i]+=len,a.num[i+1]-=1;
        if(!a.num[a.size]) a.size--;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    read(a);
    read(b);
    int t1=div(a);
    int t2=div(b);
    int t=min(t1,t2);
    while(true) {
        if(change(a,b)) { 
            time(a,t);
            write(a);
            return 0;
        }
        reduce();
        div(a);
    }
}

相比二进制算法,时间复杂度一致,但常数更小.