标签（空格分隔）： 九度OJ
原题地址：http://ac.jobdu.com/PRoblem.php?pid=1056
输入两个正整数，求其最大公约数。
测试数据有多组，每组输入两个正整数。
对于每组输入,请输出其最大公约数。
如果遍历的话会很麻烦，这里参考了书上的欧几里得算法。即：
如果求a,b的最大公约数，如果b为0，那么最大公约数为a；否则，则改为求``b``和``a % b``的最大公约数。证明我也看不懂，就不讲了。C++算法如下。
#include <stdio.h>int gcd(int a, int b) { if (b == 0) return a; else 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;}另外，是否想起了前面的java BigInteger类？没错！自带求最大公约数方法！虽然用java效率很低，但是，核心算法不用我们写，不容易错啊！ 方法如下。
import java.util.*;import java.math.*;public class Main{ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { String line =scanner.nextLine(); String[] params = line.split(" "); BigInteger a = new BigInteger(params[0]); BigInteger b = new BigInteger(params[1]); System.out.println(a.gcd(b)); } }}2017 年 3 月 6 日
新闻热点
疑难解答
