容易想到容斥原理，但是结合欧拉函数的公式，我们得到：

　　小于n且与n互质的数的和为：n * phi(n) / 2

于是问题迎刃而解。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 typedef long long ll; 7 const int MOD = 1000000007; 8  9 int euler_phi( int n )10 {11     int ans = n;12     for ( int i = 2; i * i <= n; i++ )13     {14         if ( n % i == 0 )15         {16             ans = ans / i * ( i - 1 );17             do18             {19                 n = n / i;20             }21             while ( n % i == 0 );22         }23     }24     if ( n > 1 )25     {26         ans = ans / n * ( n - 1 );27     }28     return ans;29 }30 31 int main ()32 {33     int n;34     while ( scanf("%d", &n), n )35     {36         int res = ( ll ) ( n - 1 - euler_phi(n) ) * n / 2 % MOD;37         printf("%d\n", res);38     }39     return 0;40 }