HDu 3501オーラ関数の拡張

问题描述:1つのNを与えて、1を求めます..N中のNとの互質数の和if gcd(n,i)=1 then gcd(n,n-i)=1(1<=i<=n)反証法:Kが存在する場合!=1 gcd(n,n−i)=kとすると、(n−i)%k=0、n%k=0となると、i%k=0 kがnの因子であることを保証しなければならず、i%k=0となるとgcd(n,i)=kとなり、矛盾が生じる.そこで問題は非常に簡単になりました:ANS=N*phi(N)/2 i、n-iはいつもペアで現れ、そしてnである可能性があります.もしn-i=iがあれば、それは繰り返し計算ではありませんか?答えは、n=2*i->i=n/21のためではありません.nが奇数ならn!=2*i,n-i=iと繰返し計算の説は自然に存在しない.nが偶数である場合、n=2*iが成立し、gcd(n,n/2)は必然的にnの1つの因子であり、この因子は1当であり、n=2がn>2の偶数である場合にのみ、gcd(n,n/2)=1は絶対に存在しないので、n=2 ans=2*1/2=1に対して繰り返し計算されることは言うまでもない.ちょうど満足していたので最終公式が得られた:ans=N*phi(N)/2-----------------------------以上の内容は_________から転載したコード:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MOD 1000000007

using namespace std;

long long euler ( long long num )
{
    long long res = num;
    for ( long long i = 2 ; i*i<=num ; i++ )
    {
            if ( num %i == 0 )
            {
                res -= res/i;
                while (  num%i==0 ) num /= i;
            }
    }
    if ( num > 1 ) res -= res/num;
    return res;
}

int main ( )
{
    long long ans;
    while ( ~scanf ( "%lld" , &ans ) ,ans )
        printf ( "%lld
" , (ans*(ans-1L) /2L - euler(ans)*ans/2L)%MOD );
    return 0;
}