Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!