一、定義

因數/約數：給定一個正整數 \(x\)，\(x\) 的因數/約數就是所有滿足 \(x\) 是 \(y\) 的正整數倍的 \(y\)。

最大公因數/最大公約數：給定兩個正整數 \(a\)，\(b\)，求一個最大的正整數數 \(x\)，使得它同時是 \(a\) 和 \(b\) 的因數。

一般在 OI 中記為 \((a,b)=x\)，在數學上記為 \(\gcd(a,b)=x\)。

二、求法

1. 輾轉相減法

怎么求？假設 \(a>b\)，\(\gcd(a,b)=x\)，那么發現由于 \(a\) 和 \(b\) 都是 \(x\) 的整數倍，所以 \(a-b\) 是 \(x\) 的整數倍，\(\gcd(a-b,b)\) 依然是 \(x\) 的倍數。所以 \(\gcd(a,b)|\gcd(a-b,b)\)。

反過來，假設 \(\gcd(a-b,b)=y\)，那么我們發現 \(b\) 是 \(y\) 的整數倍，并且 \(a=(a-b)+b\) 是 \(y\) 的倍數，所以 \(\gcd(a,b)\) 是 \(y\) 的的倍數。所以 \(\gcd(a-b,b)|\gcd(a,b)\)。

所以 \(\gcd(a,b)=\gcd(a-b,b)\)。

反復用大的減去小的，在有限次操作后一定有一個數變為 \(0\)，因為一開始 \(a+b\) 有限并且在 \(a,b>0\) 時 \(a+b\) 嚴格遞減。

那么此時另一個數不為 \(0\)，就是原來的 \(\gcd(a,b)\)。

時間復雜度 \(O(\max\{a,b\})\)。

這是因為我們可以令 \(b=1\)，那么就需要跑 \(a\) 次。

ll gcd(ll a,ll b){
	if(!b)return a;
	else return gcd(b,a-b);
}

2. 輾轉相除法（歐幾里得算法）

這樣要花費很久，所以可以將減換為取模。

ll gcd(ll a,ll b){
	if(!b)return a;
	else return gcd(b,a%b);
}

當然，壓壓行。

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

這樣的時間復雜度是 \(O(\log\max\{a,b\})\)。

3. 輾轉相減法的優化

如果 \(a,b\le 10^{10000}\)，該怎么辦？我們發現，高精度除法常數較大而且非常難寫。

此時我們可以考慮如下算法：假設 \(a>b\)，針對 \(a,b\) 分類，

1. \(a,b\) 中有一個是 2 的倍數，那么除以 2 就可以了。

2. \(a,b\) 都是 2 的倍數，那么全部除以 2，把答案乘 2 就可以了。

3. \(a,b\) 中沒有 2 的倍數，那么返回 \(\gcd(a,a-b)\) 就可以了。

容易知道每出現一次 3，就會出現 1、2 中的一種情況，因為奇數減奇數是偶數。所以時間復雜度是 \(O(\log\max\{a,b\})\)。壓位高精可以有效減少常數。

P2152 [SDOI2009] SuperGCD

注意這一題要高精，總時間復雜度 \(O(\log^2\max\{a,b\})\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct bigint{int l,a[1210];}p,q,tmp;
int cnt=0,bs=1000000000;//記錄 2 的次數，壓位高精 
inline void print(bigint x){
	for(int i=x.l-1;i>=0;i--){
		if(i!=x.l-1){
			if(x.a[i]<=100000000)putchar(48);
			if(x.a[i]<=10000000)putchar(48);
			if(x.a[i]<=1000000)putchar(48);
			if(x.a[i]<=100000)putchar(48);
			if(x.a[i]<=10000)putchar(48);
			if(x.a[i]<=1000)putchar(48);
			if(x.a[i]<=100)putchar(48);
			if(x.a[i]<=10)putchar(48);
		}
		cout<<x.a[i];
	}
	putchar(10);
}
inline bigint read(){
	bigint r;r.l=0;memset(r.a,0,sizeof(r.a));
	string s;cin>>s;int x=0,n=s.size(),c=n;
	for(c=n;c>=9;c-=9){
		for(int i=-9;i<0;i++)x=(x<<3)+(x<<1)+(s[c+i]^48);
		r.a[r.l++]=x,x=0;
	}
	if(c){
		for(int i=0;i<c;i++)x=(x<<3)+(x<<1)+(s[i]^48);
		r.a[r.l++]=x;
	}
	return r;
}
inline bool cmp(bigint x,bigint y){
	if(x.l^y.l)return x.l>y.l;
	for(int i=x.l-1;i>=0;i--)
		if(x.a[i]^y.a[i])return x.a[i]>y.a[i];
	return 0;
}
inline bigint sub(bigint x,bigint y){
	for(int i=x.l-1;i>=0;i--)x.a[i]-=y.a[i];
	for(int i=0;i<x.l;i++)
		if(x.a[i]<0)x.a[i]+=bs,x.a[i+1]--;
	if(!x.a[x.l-1])x.l--;
	return x;
}
inline bigint div2(bigint x){
	for(int i=0;i<x.l;i++)x.a[i]=(x.a[i+1]&1)*bs/2+x.a[i]/2;
	if(!x.a[x.l-1])x.l--;
	return x;
}
inline bigint mul2(bigint x){
	for(int i=0;i<x.l;i++)x.a[i]<<=1;
	for(int i=0;i<x.l;i++)
		if(x.a[i]>=bs)x.a[i]-=bs,x.a[i+1]++;
	if(x.a[x.l])x.l++;
	return x;
}
int main(){
	p=read();q=read();
	if(cmp(q,p))tmp=p,p=q,q=tmp;//保證 p>q 
	while(q.l){
		if((p.a[0]%2==0)&&(q.a[0]%2==0)){
			cnt++;
			p=div2(p);
			q=div2(q);
		}else if(p.a[0]%2==0)p=div2(p);
		else if(q.a[0]%2==0)q=div2(q);
		else p=sub(p,q);
		if(cmp(q,p))tmp=p,p=q,q=tmp;
	}
	while(cnt--)p=mul2(p);
	print(p);
	return 0;
}