【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d255
【解題想法】最大公因數 GCD【筆記】
#include <iostream>
#include <algorithm>
using namespace std;
int GCD(int x, int y) {
while ((x %= y) && (y %= x));
return x + y;
}
int main() {
int N, G;
while (cin >> N && N) {
G = 0;
for (int i = 1; i < N; i++) {
for (int j = i + 1; j <= N; j++) {
G += GCD(i, j);
}
}
cout << G << "\n";
}
}
Python code (credit: Amy Chou)
【解題想法】先建表,避免TLE。(測資有很多筆,但 N 的範圍不大。)
def GCD(x, y):
while True:
try:
x %= y
y %= x
except:
break
return x + y
table = [[0 for i in range(501)] for j in range(501)]
for i in range(1, 501):
for j in range(i+1, 501):
table[i][j] = GCD(i, j)
while True:
N = int(input())
if N == 0:
break
G = 0
for i in range(1, N):
for j in range(i+1, N+1):
G += table[i][j]
print(G)