hdu3501-Calculation 2

這題參考了別人的代碼，才知道原來當數據較大時求解前n 項的歐拉函數和，可以直接利用 n * enlerfun( n) / 2求解，而此題要求的是非互質的，同樣可以使用這個性質

[cpp] 
#include<iostream>  
#include<cstdio>  
#include<cstring>  
 
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 ; 
}