一、定义
因数/约数:给定一个正整数 \(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\) 分类,
-
\(a,b\) 中有一个是 2 的倍数,那么除以 2 就可以了。
-
\(a,b\) 都是 2 的倍数,那么全部除以 2,把答案乘 2 就可以了。
-
\(a,b\) 中没有 2 的倍数,那么返回 \(\gcd(a,a-b)\) 就可以了。
容易知道每出现一次 3,就会出现 1、2 中的一种情况,因为奇数减奇数是偶数。所以时间复杂度是 \(O(\log\max\{a,b\})\)。压位高精可以有效减少常数。
注意这一题要高精,总时间复杂度 \(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;
}
标签:return,gcd,int,ll,笔记,else,学习,最大公约数,bigint
From: https://www.cnblogs.com/qwq-qaq-tat/p/17356666.html