首页 > ACM题库 > 九度OJ > 九度-1056-最大公约数[解题代码]
2013
12-12

九度-1056-最大公约数[解题代码]

题目来源:2011年哈尔滨工业大学计算机研究生机试真题

题目描述:

输入两个正整数,求其最大公约数。

输入:

测试数据有多组,每组输入两个正整数。

输出:

对于每组输入,请输出其最大公约数。

样例输入:
49 14
样例输出:
7

java 代码如下:
import java.util.Scanner;

public class Main {
	static int a,b;
	static int f(int x,int y){
		
		while(y != 0){
			int tmp = y;
			y = x % y;
			x = tmp;
		}
		return x;
	}
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while(s.hasNextInt()){
			a = s.nextInt();
			b = s.nextInt();
			
			if(a < b){
				System.out.println(f(b,a));
			}else
				System.out.println(f(a,b));
			
		}
	}

}
/**************************************************************
	Problem: 1056
	User: coder
	Language: Java
	Result: Accepted
	Time:80 ms
	Memory:15496 kb
****************************************************************/


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮