HDU3501 Calculation 2(欧拉函数推广)

?

题意：求小于n的与n不互质的数的和；

分析：

欧拉函数的推广：

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

代码如下：

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std; typedef long long LL; const int mod = 1000000007; LL phi(LL n) { LL rea=n; for(int i=2;i*i<=n;i++){ if(n%i==0){ rea-=rea/i; while(n%i==0) n/=i; } } if(n>1) rea-=rea/n; return rea; } int main() { LL n; while(cin>>n){ if(n==0) break; cout<<((n-1)*n/2%mod-phi(n)*n/2%mod+mod)%mod<
     
      
?
      
?