14263: 【原4263】GCD

题目

题目描述

author: ljx 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4263

GCD

给定两个数$a,b\ (1\leq a,b \leq 10^{18})$，计算$a,b$的最大公约数$gcd(a,b)$。请使用辗转相除法。 给定的sample.cpp如下：

#include <iostream>
#include <cstdio>
using namespace std;

long long a, b;
long long ans;
long long GCD(long long a, long long b)
{
    long long ans = 0;
    //TODO
    //用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，
    //如此反复，直到最后余数是0为止。
    //如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
    //请把最后的结果在这里赋值给ans
    return ans;
}

int main()
{
    cin >> a >> b; //给定数据输入保证a>=b
    ans = GCD(a,b);
    cout << ans << endl;
    return 0;
}

读入和各个变量的定义已经为你提供，你只需要完成//TODO部分的内容。算法描述请见程序中的注释。

INPUT

第一行两个正整数，a,b，含义如题面，保证$a\geq b$

OUTPUT

一个正整数，表示$gcd(a,b)$

SAMPLE INPUT

12 3

SAMPLE OUTPUT

3

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！