24h購物| | PChome| 登入
2012-05-18 07:34:03| 人氣3,839| 回應0 | 上一篇 | 下一篇

[UVA] 11417 - GCD

推薦 0 收藏 0 轉貼0 訂閱站台

Problem A
GCD
Input: Standard Input

Output: Standard Output

 

Given the value of N, you will have to find the value of G. The definition of G is given below:

 

Here GCD(i,j) means the greatest common divisor of integer i and integer j.

 

For those who have trouble understanding summation notation, the meaning of G is given in the following code:

G=0;

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

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

{

    G+=GCD(i,j);

}

/*Here GCD() is a function that finds the greatest common divisor of the two input numbers*/

 

Input

The input file contains at most 100 lines of inputs. Each line contains an integer N (1<N<501). The meaning of N is given in the problem statement. Input is terminated by a line containing a single zero.  This zero should not be processed.

 

Output

For each line of input produce one line of output. This line contains the value of G for corresponding N.

 

Sample Input                              Output for Sample Input

10

100

500

0

 

67

13015

442011

#include <stdio.h>
int gcd(int x, int y) {
    int tmp;
    while(x%y) {
        tmp = x, x = y, y = tmp%y;
    }
    return y;
}
int main() {
    int n, i, j;
    int ans[501] = {}, map[501][501] = {};
    for(i = 1; i < 501; i++) {
        for(j = i+1; j < 501; j++) {
            map[i][j] = map[i][j-1] + gcd(i, j);
            ans[j] += map[i][j];
        }
    }
    while(scanf("%d", &n) == 1 && n) {
        printf("%d\n", ans[n]);
    }
    return 0;
}

 

我要檢舉
#11417#GCD
台長： Morris

您可能對以下文章有興趣

人氣(3,839) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 11455 - Behold my quadrangle
此分類上一篇:[UVA][組何分配] 10910 - Marks Distribution

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文