题解 | #珂朵莉的数论题#

// 与 1 互质的数有： 1
//    2          ： 1
//    3          :  1  2
//    4          :  1  3
//    5          :  1  2  3  4
//    6          :  1  5
//    7          :  1  2  3  4  5  6  
//    8          :  1  3  5  7
//    9          :  1  2  4  5  7  8
//    20         :  1  3  7  9  11 13  17  19
//    50         :  1  3  7  9  11 13  17  19 21 23 27 29 31 33 37 39 41 43 47 49
//    惊奇的发现：与 n 互质的数的和为 phi(n)*n/2,(n>1),当 n = 1 时取1；
//    所以ans = (n+1)*n/2 - n * phi(n)/2;

#include<iostream>
#define int long long 
using namespace std;
const int p=1e9+7;
int phi(int x)
{
    int res=x;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            res = res / i * (i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1)res = res / x * (x-1);
    return res;
}

signed main()
{
    int n,ans,t;
    while(cin>>n)
    {
        ans =0;
        if(n==1)
        {
            cout<<0<<endl;
            continue;
        }
        t=phi(n);
        if(n%2==0)
        {
            ans = (n/2%p * ((n+1)%p))%p;
            ans %= p;
            ans -= ((n/2)%p * (t%p))%p;
            ans = (ans % p + p) % p;
        }
        else 
        {
            ans = (n%p * ((n+1)/2%p))%p;
            ans %= p;
            ans -= (n%p * (t/2%p))%p;
            ans = (ans % p + p) % p;
        }
        cout<<ans<<endl;
    }
}