UVA 11417 GCD Solution

Problem Type GCD
Problem Difficulty Easy
Problem Link

Problem Statement

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

---

Problemsetter: Shahriar Manzoor

Special Thanks: Syed Monowar Hossain

Solution

 

#include <cstdio>
#include <algorithm>

using namespace std;

long long ans[210000];
int gcd[501][501];
//Time : 0.016

int main()
{
    for(int i = 2; i < 500; i++){
        for(int j = i; j <= 500; j += i){
            gcd[i][j] = i;
        }
    }
 ans[0] = 0;
 for (int n = 1; n <= 500; n++) {
  ans[n] = ans[n-1];
  for (int i = 1; i < n; i++)
   ans[n] += (!gcd[i][n])?gcd[i][n] = __gcd(i,n) : gcd[i][n];

 }

 int N;
    while(scanf("%d",&N) && N)
        printf("%lld\n",ans[N]);
}