標簽（空格分隔）： 九度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 日
新聞熱點
疑難解答
