題目
Sheng bill有著驚人的心算能力，甚至能用大腦計算出兩個巨大的數的GCD（最大公約 數）！因此他經常和別人比
賽計算GCD。有一天Sheng bill很囂張地找到了你，并要求和你比 賽，但是輸給Sheng bill豈不是很丟臉！所以你
決定寫一個程序來教訓他。
輸入格式
共兩行： 第一行：一個數A。 第二行：一個數B。
0 < A , B ≤ 10 ^ 10000。
輸出格式
一行，表示A和B的最大公約數。
輸入樣例
12
54
輸出樣例
6
題解
時隔大半年，我回來A這道題啦【當初寫的太BUG了】
求GCD，很容一想到輾轉相除，而高精不好操作取模，這就用到了輾轉相除法的本質：更相減損法
GCD(a,b) = GCD(a,a-b) 【a >ｂ】
然而這樣會T，所以我們還要優化：
GCD(a,b) = 2*GCD(a/2,b/2) 【2|a且2|b】
GCD(a,b) = GCD(a/2,b) 【2|a】
GCD(a,b) = GCD(a,b/2) 【2|b】
GCD(a,b) = GCD(a,a-b) 【a >ｂ】
加上個壓位高精【高精減法，高精除低精，高精乘低精，高精比較】
就可以A了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
using namespace std;
const int maxn =
10005,B =
4,Base =
10000,maxm =
100005,INF =
1000000000;
struct NUM{
int s[maxn],len;NUM() {
memset(s,
0,
sizeof(s)); len =
0;}
};
istream&
operator >>(istream& in,NUM& a){
string s;in>>s;
int temp =
0,t =
1;
for (
int i = s.length() -
1; i >=
0; i--){temp = temp + t * (s[i] -
'0');
if (t *
10 == Base) a.s[++a.len] = temp,temp =
0,t =
1;
else t *=
10;}
if (temp) a.s[++a.len] = temp;
return in;
}
ostream&
operator <<(ostream& out,
const NUM& a){
if (!a.len) out<<
0;
else {
printf(
"%d",a.s[a.len]);
for (
int i = a.len -
1; i >
0; i--)
printf(
"%04d",a.s[i]);}
return out;
}
bool check(
const NUM& a){
return !(a.s[
1] &
1);}
bool equal(
const NUM& a,
const NUM& b){
if (a.len != b.len)
return false;REP(i,a.len)
if (a.s[i] != b.s[i])
return false;
return true;
}
bool operator <(
const NUM& a,
const NUM& b){
if (a.len < b.len)
return true;
if (a.len > b.len)
return false;
for (
int i = a.len; i >
0; i--){
if (a.s[i] < b.s[i])
return true;
if (a.s[i] > b.s[i])
return false;}
return false;
}
void Half(NUM& a){
int carry =
0,temp;
for (
int i = a.len; i >
0; i--){temp = (a.s[i] + carry * Base) /
2;carry = a.s[i] + carry * Base - temp *
2;a.s[i] = temp;}
while (!a.s[a.len]) a.len--;
}
void Twice(NUM& a){
int carry =
0,temp;
for (
int i =
1; i <= a.len; i++){temp = a.s[i] *
2 + carry;a.s[i] = temp % Base;carry = temp / Base;}
while (carry) a.s[++a.len] = carry % Base,carry /= Base;
}
NUM
operator -(
const NUM& a,
const NUM& b){NUM c; c.len = a.len;
int carry =
0,temp;
for (
int i =
1; i <= a.len; i++){temp = a.s[i] - b.s[i] + carry;
if (temp <
0) carry = -
1,temp += Base;
else carry =
0;c.s[i] = temp;}
while (!c.s[c.len]) c.len--;
return c;
}
int main(){NUM A,B;
int cnt =
0;
cin>>A>>B;
while (!equal(A,B)){
if (check(A) && check(B)) Half(A),Half(B),cnt++;
else if (check(A)) Half(A);
else if (check(B)) Half(B);
else {
if (B < A) swap(A,B);B = B - A;}}
while (cnt--) Twice(A);
cout<<A<<endl;
return 0;
}
轉載于:https://www.cnblogs.com/Mychael/p/8282745.html
總結
以上是生活随笔為你收集整理的BZOJ1876 [SDOI2009]SuperGCD 【高精 + GCD优化】的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
