这题参考了别人的代码，才知道原来当数据较大时求解前n 项的欧拉函数和，可以直接利用 n * enlerfun( n) / 2求解，而此题要求的是非互质的，同样可以使用这个性质
[cpp]
#include
#include
#include
using namespace std ;
#define MOD 1000000007
#define INT __int64
INT enlerfun(INT n )
{
INT ans = n ;
for( INT i = 2 ; i * i <= n ; ++i )
{
if( n % i == 0 )
{
ans = ans / i * ( i - 1 ) ;
while( n % i == 0 )
{
n /= i ;
}
}
if( n > 1 )
ans = ans / n * ( n - 1 );
return ans ;
}
int main()
{
INT n ;
while( ~scanf( "%I64d" , &n ) , n )
{
INT num = n - 1 - enlerfun( n ) ;
num = ( n * num / 2 ) % MOD ;
while( n < 0 )
num += MOD ;
printf( "%I64d\n" , num ) ;
}
return 0 ;
}