381 最大公约数 - Tomorrow I will do the programming.

问题描述

求两个整数的最大公约数是一个很有价值的问题，给定整数a和b，下面的方法可以较快速的求出a和b的最大公约数。
如果a是b的倍数，则a和b的最大公约数为b，否则a和b的最大公约数等于b和a%b的最大公约数。其中a%b表示a除b的余数。
如，要求48和72的最大公约数，用(48,72)来表示，则可以按下面的过程来求：
(48,72)=(72,48)=(48,24)=24。
给出a和b，用递归的方式来求a和b的最大公约数。

输入格式

输入的第一行包含两个整数a, b。

输出格式

输出两个数的最大公约数。

样例输入

48 72

样例输出

#include <iostream>

#include <cstdlib>

#include <cstdio>

using namespace std;

int gcd(int a, int b)

{

if (a==0) return b;

else return gcd(b%a,a);

}

int main()

{

int a, b;

cin >> a >> b;

cout << gcd(a, b) << endl;

return 0;

}

posted on 2010-03-20 15:04 jyy 阅读(156) 评论(0) 编辑收藏引用所属分类: OJ平台

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

程序设计基础

牛们

搜索

最新评论

阅读排行榜

评论排行榜

只有注册用户登录后才能发表评论。


相关文章: 链表、队列、栈 381 最大公约数 116 字符统计 115 字符串对比 114 瓷砖问题再讨论 113 瓷砖铺放(Tile) 112 数列倒序(Reverse) 111 求小于M的素数 110 求Fibonacci数 109 求n!

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理