CPE 一顆星選集 49 道必考題
題目連結:https://zerojudge.tw/ShowProblem?problemid=d255
內容
G=0;
for(i=1;i < N;i++)
for(j=i+1;j<=N;j++)
{
G+=GCD(i,j);
}
/* GCD()為一個求兩個輸入數字的最大公因數的函數*/
給定 N(1 < N < 501)，輸出 G。
N = 0 代表結束。
範例輸入
10
100
500
0
範例輸出
67
13015
442011
想法
跟著題目走。
可用內建函式 __gcd(i, j)。
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
int main(){
fastio;
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";
}
return 0;
}
|