可以用GCD也可以用欧拉函数。
#include <stdio.h>
#include <math.h>

const int MAX = 1002;

int prime[MAX];
int len = 0;

int dp[MAX];

int check ( int n )/*??????????????*/
{
    if ( !( n & 1 ) )
    {
        return 2;
    }

    int m = (int)sqrt ( (double)n );

    int l, r, mid;
    l = 0;
    r = len-1;
    while ( l <= r )
    {
        mid = ( l+r ) / 2;
        if ( prime[mid] > m )
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    for ( int i=0; i<=r; i++ )
    {
        if ( n % prime[i] == 0 )
        {
            return prime[i];
        }
    }
    prime[len++] = n;
    return n;
}

void cup ()
{

    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 2;
    dp[4] = 2;
    dp[5] = 4;
    prime[0] = 2;
    prime[1] = 3;
    prime[2] = 5;
    len = 3;
    for ( int i=6; i<MAX; i++ )
    {
        int min = check ( i );

        if ( (i / min) % min )
        {
            dp[i] = dp[i/min]*(min-1);
        }
        else
        {
            dp[i] = dp[i/min]*min;
        }
    }

    dp[1] = 3;
    for ( i=2; i<MAX; i++ )
    {
        dp[i] = dp[i]*2+dp[i-1];
    }
}

int main ()
{

    int t;
    int n;

    cup ();

    scanf ( "%d", &t );

    for ( int i=1; i<=t; i++ )
    {
        scanf ( "%d", &n );
        printf ( "%d %d %d\n", i, n, dp[n] );
    }
    return 0;
}