BZOJ 1876: [SDOI2009]SuperGCD( 更相减损 + 高精度 )

时间：2021-07-02 19:38:50

BZOJ 1876: [SDOI2009]SuperGCD( 更相减损 + 高精度 )

更相减损，要用高精度....

---------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn = 10009;
char S[maxn];
int Power[maxn];
struct BigInt {
static const int B = 10000000;
static const int W = 7;
static const int MAXN = 10000;
int n, s[MAXN];
BigInt() {
n = 0;
memset(s, 0, sizeof s);
}
bool operator < (const BigInt &t) const {
if(n != t.n) return n < t.n;
for(int i = n; i--; )
if(s[i] != t.s[i]) return s[i] < t.s[i];
return true;
}
bool operator != (const BigInt &t) const {
return (*this < t) != (t < *this);
}
BigInt operator -= (const BigInt &t) {
for(int i = 0; i < t.n; i++) {
if(s[i] < t.s[i])
s[i] += B, s[i + 1]--;
s[i] -= t.s[i];
}
for(int i = t.n; i < n; i++) if(s[i] < 0)
s[i] += B, s[i + 1]--;
while(n > 0 && !s[n - 1]) n--;
return *this;
}
void Read() {
scanf("%s", S);
int N = strlen(S), p = N; n = N / W;
for(int i = 0; i < n; i++) {
for(int j = p - W; j < p; j++)
s[i] = s[i] * 10 + S[j] - '0';
p -= W;
}
if(N % W) {
for(int i = 0; i < p; i++)
s[n] = s[n] * 10 + S[i] - '0';
n++;
}
}
void Write() {
for(int i = n; i--; ) {
if(i != n - 1) {
int t = 0;
for(int v = s[i]; v; v /= 10) t++;
if(!t) t++;
while(t < W)
putchar('0'), t++;
}
printf("%d", s[i]);
}
putchar('\n');
}
inline bool chk() {
return n == 1 && s[0] == 1;
}
inline bool Even() {
return !(s[0] & 1);
}
void Div2() {
for(int i = n; i--; ) {
if(s[i] & 1)
s[i - 1] += B;
s[i] >>= 1;
}
if(!s[n - 1]) n--;
}
void Mul2() {
for(int i = n; i--; ) s[i] <<= 1;
for(int i = 0; i < n; i++)
if(s[i] >= B) s[i] -= B, s[i + 1]++;
if(s[n]) n++;
}
} A, B, *a = &A, *b = &B;
int main() {
a->Read(); b->Read();
int cnt = 0;
while(*a != *b) {
if(a->chk()) break;
if(a->Even()) {
a->Div2();
if(b->Even()) b->Div2(), cnt++;
} else if(b->Even()) {
b->Div2();
} else {
if(*b < *a) swap(b, a);
*b -= *a;
}
}
while(cnt--) a->Mul2();
a->Write();
return 0;
}

---------------------------------------------------------------

1876: [SDOI2009]SuperGCD

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 2277  Solved: 770
[Submit][Status][Discuss]

Description

Sheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约 数）！因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你，并要求和你比 赛，但是输给Sheng bill岂不是很丢脸！所以你决定写一个程序来教训他。

Input

共两行： 第一行：一个数A。 第二行：一个数B。

Output

一行，表示A和B的最大公约数。

Sample Input

12
54

Sample Output

6

HINT

对于20%的数据，0 < A , B ≤ 10 ^ 18。
对于100%的数据，0 < A , B ≤ 10 ^ 10000。

Source

相关文章