d255: 11417 - GCD
Tags :
Accepted rate : 1356人/1410人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2009-05-13 16:09

Content

已知 的值,你必須求 G的定義如下:

 

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

 

如果看不懂Sigma表示方式的話,的定義則如以下的程式碼:

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)的定義如題幹。輸入以含有一個 0 的一行作為結束,請不要處理這個 0
Output
就每行的輸入產生一行輸出。這行含有相對於 的 G
Sample Input
10
100
500
0
Sample Output
67
13015
442011
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <1K
Hint :
* 中文翻譯:板橋高中
Tags:
出處:
UVa11417 [管理者:
pcsh710742 (ms0472904)
]


ID User Problem Subject Hit Post Date
18962
CSE210617 (A_A)
d255
加速方法
190 2019-08-18 15:08
18961
CSE210617 (A_A)
d255
加速方法
93 2019-08-18 14:59