http://www.spoj.pl/problems/LCMSUM/

 sigma lcm( i, n )  =  sigma ( i * n / gcd( i, n ) )  = n * sigma ( i / gcd( i, n ) )
设 gcd( i, n ) = k,  i = k * j, n = k * m ( j <= m ) ，所以
只要枚举n的每个因数，对于每个因数q,求出小于等于q,且与q互素的数的和，将所有的和加起来就是答案了

（1）对于小于等于q，且与q互素的数的和，有公式 q * phi( q ) / 2，具体证明如下：
    小于N且与N互质的正整数之和, 设为S.
    不妨设这些数为a[1], a[2], ..., a[ phi(N) ], 其中phi(N)是N的欧拉函数值.
    对1 <= i <= phi(N), 由gcd( N, a[i] ) = 1可知gcd( N, N - a[i] ) = 1.
    这里可以采用反证: 设gcd( N, N - a[i] ) = k >  1,
    则 k | N,  k | ( N - a[i] )  ->  k | a[i]  ->  k | gcd( N, a[i] ), 而gcd( N , a[i] ) = 1, 矛盾.
    这样, N - a[1], N - a[2], ..., N - a[ phi(N) ]也对应着原数列, 则有:
    S = a[1] + a[2] + ... + a[ phi(N) ]
    S = (N - a[1]) + (N - a[2]) + ... + (N - a[ phi[N] ])
    两式相加得: S = N * phi(N) / 2.
（2）这题n比较小，可以先预处理1到n的所欧拉函数。
（3）1是特殊情况，我的程序会少算一个1，所以最后加回去了。

 1#include <stdio.h>
 2#include <iostream>
 3#include <map>
 4#include <queue>
 5#include <complex>
 6#include <algorithm>
 7#include <cmath>
 8#include <cstring>
 9using namespace std;
10typedef long long ll;
11const int maxn = 1010;
12int p[maxn], vis[maxn], plen;
13int num[40], fac[40], flen;
14ll ans;
15int phi[1000010];
16
17void prime( )
18{
19    int i, j, k;
20    plen = 0;
21    memset( vis, 0, sizeof( vis ) );
22    for( i = 2, k = 4; i < maxn; ++i, k += i + i - 1 )
23    {
24        if( !vis[i] )
25        {
26            p[plen++] = i;
27            if( k < maxn ) for( j = k; j < maxn; j += i ) vis[j] = 1;
28        }
29    }
30}
31
32void all_phi( int n )
33{
34    int i, j;
35    memset( phi, 0, sizeof( phi ) );
36    phi[1] = 1;
37    for( i = 2; i <= n; i++ )
38    {
39        if( !phi[i] )   //prime
40            for( j = i; j <= n; j += i )  // for each multiple
41            {
42                if( !phi[j] ) phi[j] = j;  // first time , initialize
43                phi[j] = phi[j] / i * ( i - 1 );
44            }
45    }
46}
47
48void init( )
49{
50    prime( );
51    all_phi( 1000000 );
52}
53
54void dfs( int dep, int k )
55{
56    if( dep == flen )
57    {
58        ans += (ll)phi[k] * k / 2;
59        return;
60    }
61    ll tmp = 1;
62    for( int i = 0; i <= num[dep]; i++ )
63    {
64        dfs( dep + 1, k * tmp );
65        tmp *= fac[dep];
66    }
67}
68
69int main(int argc, char *argv[])
70{
71    int t, n, nn, i;
72    init( );
73    scanf("%d",&t);
74    while( t-- )
75    {
76        scanf("%d",&n);
77        nn = n;
78        flen = 0;
79        for( i = 0; p[i] * p[i] <= n; i++ )
80        {
81            if( !( n % p[i] ) )
82            {
83                for( num[flen] = 0; n % p[i] == 0; ++num[flen], n /= p[i] );
84                fac[flen++] = p[i];
85            }
86        }
87        if( n > 1 ) num[flen] = 1, fac[flen++] = n;
88        ans = 0;
89        dfs( 0, 1 );
90        printf("%lld\n",(ans+1)*nn);
91    }
92    return 0;
93}
94