问题 F: 二进制求最大公约数

内存限制:125 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:77 通过:44

题目描述

二进制最大公约数算法

  递归终止条件:gcd(m,m)=m

  递归关系式:

m<n时:gcd(m,n)=gcd(n,m)

m,n均为偶数:gcd(m,n)=2*gcd(m/2,n/2)

m为偶数,n为奇数:gcd(m,n)=gcd(m/2,n)

m数,n为偶数:gcd(m,n)=gcd(m,n/2)

m为奇数,n为奇数:gcd(m,n)=gcd(n,m-n)

输入格式

输入两个正整数m,n,两个数之间用空格隔开。

输出格式

输出mn的最大公约数

输入样例 复制

4 8

输出样例 复制

4

分类标签