M_sea

洛谷2152 [SDOI2009]SuperGCD
gcd+高精=省选大火题。。。题目描述Sheng bill有着惊人的心算能力,甚至能用大脑计算出两个巨大的数的GC...
扫描右侧二维码阅读全文
19
2017/11

洛谷2152 [SDOI2009]SuperGCD

gcd+高精=省选大火题。。。

题目描述

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

传送门

算法

数论板子题。。。

大家都知道gcd(a,b)=gcd(b,a%b),但是gcd还有更优的形式:

  • 若a是奇数,b是偶数,则$gcd(a,b)=gcd(a,b/2)$。
  • 若a是偶数,b是奇数,则$gcd(a,b)=gcd(a/2,b)$。
  • 若a是偶数,b是偶数,则$gcd(a,b)=2*gcd(a/2,b/2)$。
  • 若a是奇数,b是奇数,则$gcd(a,b)=gcd(a-b,b)\ (a>b)$。

然后套上高精就好了。记得要压位(压八位最好了)。

代码

然而这题不一定要用C++写啊【滑稽】
Java自带BigInteger和gcd,多完美:

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin=new Scanner(new BufferedInputStream(System.in));
        BigInteger a,b;
        a=cin.nextBigInteger();
        b=cin.nextBigInteger();
        System.out.println(a.gcd(b));
    }
}

或者说python也好(注意空行的坑):

//Author:xzz 大佬
s=[]
while True:
    try:
        Str=input()
        while Str.find('  ')==0:Str=Str.replace('  ',' ')
        if Str==' ' or Str=='':continue
        if Str[0]==' ':Str=Str[1:len(Str)]
        if Str[-1]==' ':Str=Str[0:len(Str)-1]
        if Str.count(' ')==0:s.append(Str)
        else:s+=Str.split(' ')
    except:break
a,b=map(int,s)
while(b!=0):a,b=b,a%b
print(a)

C++也不是不行(高精什么的自己去写吧):

inline BigInteger gcd(BigInteger& a,BigInteger& b) {
    if (a<b) swap(a,b);
    if (a%b==0) return b;
    if (a%2==0) {
        if (b%2==0) return gcd(a/2,b/2)*2;
        else return gcd(a/2,b);
    }
    else {
        if (b%2==0) return gcd(a,b/2);
        else return gcd(a-b,b);
    }
}
最后修改:2018 年 11 月 09 日 04 : 32 PM

发表评论