1. Java, Till Fischer
/*

 ============================================================================

 Author            : Till Fischer

 Description    : 11417 - GCD - The version with memory

 Accepted        : yes

 Time            : 0.240

 ============================================================================

 */



import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;



public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(

                System.in));

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(

                System.out));

       

        String line;

        int n, g, i, j, gcd;

        int[][] memory = new int[501][501];

       

        while (!(line = reader.readLine()).equals("0")) {

            n = Integer.parseInt(line);

            g = 0;

            for (i = 1; i < n; i++) {

                for (j = i + 1; j <= n; j++) {

                    if(memory[i][j] != 0) {

                        g += memory[i][j];

                    } else {

                        gcd = gcd(i,j);

                        memory[i][j] = gcd;

                        g += gcd;

                    }

                }

            }

            writer.write(g + "\n");

        }



        // always be nice to streams!

        reader.close();

        writer.flush();

        writer.close();

    }



    private static int gcd(int a, int b) {

       if (b==0) {

           return a;

       }

       return gcd(b,a%b);

    }



}



2. Java, Till Fischer


/*

 ============================================================================

 Author            : Till Fischer

 Description    : 11417 - GCD - The stupid version

 Accepted        : yes

 Time            : 0.790

 ============================================================================

 */



import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;



public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(

                System.in));

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(

                System.out));

       

        String line;

        int n, g, i, j;



        while (!(line = reader.readLine()).equals("0")) {

            n = Integer.parseInt(line);

            g = 0;

            for (i = 1; i < n; i++) {

                for (j = i + 1; j <= n; j++) {

                    g += gcd(i,j);

                }

            }

            writer.write(g + "\n");

        }



        // always be nice to streams!

        reader.close();

        writer.flush();

        writer.close();

    }



    private static int gcd(int a, int b) {

       if (b==0) {

           return a;

       }

       return gcd(b,a%b);

    }



}


3. C++, Evgeni Pavlidis

/**
* ACM programming Contest WS 08/09
* UVa Status: accepted
* Run Time: 0.550
* Category: -
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
#include <iostream>

using namespace std;


int gcd(int a, int b)
{
return ( b == 0 ? a : gcd(b, a % b) );
}


int main()
{
int n;
while(true)
{
cin >> n;
if(n==0)
return 0;

int G=0;

for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
G+=gcd(i,j);

cout << G << endl;

}

}



4. Java, Till Fischer


/*

 ============================================================================

 Author            : Till Fischer

 Description    : 11417 - GCD - The dynamic self-optimizing version

 Accepted        : no TLE

 Time            : > 2.000

 ============================================================================

 */



import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.util.HashMap;



public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(

                System.in));

        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(

                System.out));

        HashMap<Integer[], Integer> gcdMap = new HashMap<Integer[], Integer>();

       

        String line;

        int n, g, i, j, gcd;



        while (!(line = reader.readLine()).equals("0")) {

            n = Integer.parseInt(line);

            g = 0;

            for (i = 1; i < n; i++) {

                for (j = i + 1; j <= n; j++) {

                    if(gcdMap.containsKey(new Integer[]{i,j})) {

                        g+= gcdMap.get(new Integer[]{i,j});

                    } else {

                        gcd = gcd(i, j);

                        g += gcd;

                        gcdMap.put(new Integer[]{i,j}, gcd);

                    }

                }

            }

            writer.write(g + "\n");

        }



        // always be nice to streams!

        reader.close();

        writer.flush();

        writer.close();

    }



    private static int gcd(int a, int b) {

       if (b==0) {

           return a;

       }

       return gcd(b,a%b);

    }



}