题目描述
输入两个正整数,求其最大公约数。
输入
测试数据有多组,每组输入两个正整数。
输出
对于每组输入,请输出其最大公约数。
样例输入
49 14
样例输出
7
提示 [+]
*** 提示已隐藏,点击上方 [+] 可显示 ***
来源
2011年哈尔滨工业大学计算机研究生机试真题
/********************************* * 日期:2013-3-4 * 作者:SJF0115 * 题号: 天勤OJ 题目1049: 最大公约数 * 来源:http://acmclub.com/problem.php?id=1049 * 结果:AC * 来源:2011年哈尔滨工业大学计算机研究生机试真题 * 总结: **********************************/ #include<stdio.h> int GCD(int a,int b) { //如果a < b if(a < b){ return GCD(b,a); } if(b == 0){ return a; } else{ return GCD(a - b,b); } } int main(){ int a,b; while(scanf("%d %d",&a,&b) != EOF){ printf("%d\n",GCD(a,b)); } return 0; }
/********************************* * 日期:2013-3-4 * 作者:SJF0115 * 题号: 天勤OJ 题目1049: 最大公约数 * 来源:http://acmclub.com/problem.php?id=1049 * 结果:AC * 来源:2011年哈尔滨工业大学计算机研究生机试真题 * 总结: **********************************/ #include<stdio.h> //递归形式 int GCD(int a,int b) { if(b == 0){ return a; } else{ //a,b和b,a%b有相同的最大公约数 return GCD(b,a%b); } } int main(){ int a,b; while(scanf("%d %d",&a,&b) != EOF){ printf("%d\n",GCD(a,b)); } return 0; }
/********************************* * 日期:2013-3-4 * 作者:SJF0115 * 题号: 天勤OJ 题目1049: 最大公约数 * 来源:http://acmclub.com/problem.php?id=1049 * 结果:AC * 来源:2011年哈尔滨工业大学计算机研究生机试真题 * 总结: **********************************/ #include<stdio.h> //判断奇偶性 int IsEvenOdd(int n){ if(n % 2 == 0){ return 1; } else{ return 0; } } int GCD(int a,int b) { //如果a < b if(a < b){ return GCD(b,a); } if(b == 0){ return a; } //若x,y都为偶数 if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 1){ return 2 * GCD(a>>1,b>>1); } //若x,y都为奇数 else if(IsEvenOdd(a) == 0 && IsEvenOdd(b) == 0){ return GCD(b,a-b); } //若x是偶数y是奇数 else if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 0){ return GCD(a>>1,b); } //若x是奇数y是偶数 else{ return GCD(a,b>>1); } } int main(){ int a,b; while(scanf("%d %d",&a,&b) != EOF){ printf("%d\n",GCD(a,b)); } return 0; }
具体解析详见:编程之美读书笔记(5)最大公约数
相关推荐
2.编写两个函数,分别求两个整数的最大公约数和最小公倍数
从键盘输入两个正整数,求这两个正整数的最小公倍数和最大公约数,并输出。 输入 输入包括一行。 两个以空格分开的正整数。 输出 两个整数的最小公倍数和最大公约数。 样例输入 6 8 样例输出 24 2
对输入1-100内的两个整数,求其最大公约数,输入一个0-500的整数,判断其能否被3,5,7整除,并输入下列信息之一: (1) 能够同时被3,5,7整除 (2) 能够同时被其中两个数整除(给出这两个数) 进行白盒测试
输入两个正整数m和n,求其最大公约数和最小公倍 数。
用最大公因数或最小公倍数解决问题的题目.doc
有一个文件,其中含有一些整数对,求出这些整数对的最大公约数,并对这些最大公约数按从小到达的顺序排序输出
C语言上机题目.rar 包括冒泡,最大公约数,最小公倍数,等
这是一个算法设计的题目,要求以三种方式实现最大公约数的求法,包括欧几里得法,循环测试法,质因数分解法。代码中可能没有整理好,还有一部分的质因数求法的算法。大家共同努力。
最大公约数的求法,用VS实现的,比较基础
最大公因数(Greatest Common Divisor,简称GCD),也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。整数m和n的最大公约数记为GCD(m, n)。 最小公倍数(Least Common Multiple,简称LCM)是指两个...
对于给定的2个正整数a,计算a和b之间约束个数最多的数
Python编程题目--最大公约数和最小公倍数
C语言中求最大公约数和最小公倍数的各种算法的总结,辗转相除法,穷举法等等
题目:求最大公约数 输入一组正整数(数量小于20),输出其最大公约数。 输入:121 33 44 11 1111 输出:11 基本思路: 从第一个数开始,和第二个数比较找它两的最大公约数,然后找出的最大公约数和第三个数比较,...
。。。
title: Maximum GCD(最大公约数)categories: [算法题解]传送门:UVA 11827 - Maximum GCD题目大意:给你几组数
# 我们经常遇到的问题是给你两个数,要你求最大公约数和最小公倍数。今天我们反其道而行之,给你两个数a和b, # 计算出它们分别是哪两个数的积的最大公约数和最小公倍数。输出这两个数,小的在前,大的在后,以空格...
题目:输入两个正整数m和n,求其最大公约数。 /**提示:在循环中,只要除数不等于0,用较大数除以较小的数,将小的一个数作为下一轮循环的大数,取得的余数作为下一轮循环的较小的数, 如此循环直到较小的数的值为0...
主要介绍了c++ 实现求最大公约数和最小公倍数的相关资料,需要的朋友可以参考下