高中生程式解題系統 d255: 11417 - GCD－資工趴趴熊的小天地

Content

已知 N 的值，你必須求 G。G 的定義如下：

其中 GCD(i,j) 為整數 i 和整數 j 的最大公因數。

如果看不懂Sigma表示方式的話，G 的定義則如以下的程式碼：

G=0;

for(i=1;i<N;i++)

for(j=i+1;j<=N;j++)

{

G+=GCD(i,j);

}

/* GCD()為一個求兩個輸入數字的最大公因數的函數*/

Input

輸入檔最多有 100 行的輸入。每一行有一個整數N (1<N<501)。N 的定義如題幹。輸入以含有一個 0 的一行作為結束，請不要處理這個 0。

Output

就每行的輸入產生一行輸出。這行含有相對於 N 的 G。

Sample Input #1

Sample Output #1

67
13015
442011

python:

def gcd(m,n):
    r=0
    while n!=0:
        r=m%n
        m,n=n,r
    return m
    
#這種題目就是考測資的，python的話就是要建表
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:
    try:
        n=int(input())
        g=0
        if n==0:break
        for i in range(1,n):
            for j in range(1+i,n+1):
                g+=table[i][j]
        print(g)
    except:
        break

C++:

#include <iostream>
using namespace std;


int GCD(int a,int b){
	while(b!=0){
		int t=b;
		b=a%b;
		a=t;
	}
	return a;
}
/**-----------------*/
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	while(cin>>n){
		if(n==0)break;
		int 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;
}