UVa11417 - GCD－awesq123的部落格

Give you number 'N'.

Print the sum of

GCD(1, 2),

GCD(1, 3),

...

GCD(1, N),

GCD(2, 3),

GCD(2, 4),

...

GCD(2, N),

...

GCD(3, N),

...

GCD(N-1, N)

----

#include <stdio.h>

#define MAX 500

int GCD(int i,int j);

int main(int argc, char *argv[])
{
   int i, j;
   int num, G;/* 2 <= num <= 500 */ /* The max of G is 44xxxx. So we can use the "int" */
   int table_G[MAX+1];

   /* initialize */
   for(i = 2; i <= 500; i++)
       table_G[i] = -1;

   while(scanf("%d", &num) && (num > 0))
   {
       if(table_G[num] == -1) /* == -1 shows that the value haven't been evaluated. */
       {
           for(i = 1, G = 0; i < num; i++)
               for(j = i + 1; j <= num; j++)
                   G += GCD(i,j);

           table_G[num] = G;
       }
       printf("%d\n", table_G[num]);
   }
   return 0;
}

int GCD(int i,int j) /* Greatest common divisor. */
{
   for(; i && j; ) /* Euclidean algorithm */
       if(i > j)
           i -= j;
       else
           j -= i;

   return ((!i) ? j : i); /* if i == 0 return j else return i */
}

----

package uva11417;

import java.util.Arrays;
import java.util.Scanner;

/**
*
* @author awesq
*/
public class UVa11417 {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
final int UNKNOWN = -1, MAX = 502;
int[][] table = new int[MAX][MAX];
for (int i = 0; i < MAX; i++) {
Arrays.fill(table[i], UNKNOWN);
}

try (Scanner sc = new Scanner(System.in)) {
while (sc.hasNextInt()) {
int N = sc.nextInt(), G = 0;
if (N == 0) {
break;
}

for (int i = 1; i < N; i++) {
for (int j = i + 1; j <= N; j++) {
if (table[i][j] == UNKNOWN) {
table[i][j] = getGCD(i, j);
G += table[i][j];
} else {
G += table[i][j];
}
}
}
System.out.println("" + G);
}
} catch (Exception e) {
}
}

public static int getGCD(int a, int b) {
if (b == 0) {
return a;
}
return getGCD(b, a % b);
}
}