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

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

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
10
100
500
0
Sample Output #1
67
13015
442011
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <1K
Hint :
* 中文翻譯:板橋高中
Tags:
出處:
UVa11417 [管理者: pcsh710742 (ms0472904) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
31108 andrewlintw0 ... (✦地獄幽林✧) d255
以空間換取時間
1300 2022-07-12 09:45
18962 CSE210617 (A_A) d255
加速方法
3239 2019-08-18 15:08
18961 CSE210617 (A_A) d255
加速方法
1600 2019-08-18 14:59