[Java] UVa 11417 GCD

題目連結

題意:
給定 N 值( 1 < N < 501)
求 1 ~ N 之間任兩數(i, j)的 GCD (最大公因數)總和 G
其中 1 ≦ i ＜ j ≦ N

若 N 為 3
G = GCD(1, 2) + GCD(1, 3) + GCD(2, 3)

解法:
題目上不但有題意
甚至連程式碼都給了
只需額外撰寫 GCD 的求法即可

GCD的實作大多是透過輾轉相除法
即重複執行大者減小者

1. 當其中一方結果為1，代表互質
2. 當其中一方結果為0，則另一方為GCD

 %運算(取餘數)恰好符合這種運作
前者無限次扣掉後者，直到小於後者的值
如 5%2 = 5-2-2=1 / 14%9 = 14-9 = 5

我們遞迴執行取餘數，如 GCD(a,b) = GCD(b, a%b)
每次的 b 代入成新的 a
新的 b 則為 a%b，也就是上一輪的結果
當一方為0時停止，另一方會為 1 或 GCD

例如: (以遞迴GCD的 a, b表示)
(14, 9) -  (9, 5) - (5, 4) - (4, 1) - (1, 0) 則互質
(18, 12) - (12, 6) - (6, 0) 則 GCD = 6

程式(Java):

	import java.util.*;
	public class Main {
	public static int GCD(int i, int j) {
	return (j == 0) ? i : GCD(j, i%j);
	}
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	while (sc.hasNext()) {
	int G = 0;
	int N = sc.nextInt();
	if (N == 0)
	break;
	for (int i = 1; i < N; i++)
	for (int j = i + 1; j <= N; j++)
	G += GCD(i, j);
	System.out.println(G);
	}
	}
	}

view raw UVa11417.java hosted with ❤ by GitHub