C++14(g++5.4) 解法, 执行用时: 510ms, 内存消耗: 352K, 提交时间: 2018-11-19 18:19:15

#include<iostream>
#include<cmath>
using namespace std;
#define mod 1000000007
long long int eular(long long int n)
{
	long long int res=n,m=n;
	for(int i=2;i<=sqrt(m);i++)
	{
		if(m%i==0)
		{
			res=res/i*(i-1);
		}
		while(m%i==0)
		m=m/i;
	}
	if(m>1)
	{
		res=res/m*(m-1);
	}
	return res;
}
int main()
{
	long long int n;
	while(cin>>n)
	{
		long long int ans;
		long long d;
		long long t,s;
		t=n%mod;
		s=eular(n);
		d=(n+1-s)%mod;
		if(n%2==0)
		t=n/2%mod;
		else
		d=(n+1-eular(n))/2%mod;
		cout<<(t*d)%mod<<endl;
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 182ms, 内存消耗: 424K, 提交时间: 2023-01-04 19:07:47

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,r,t,m=1e9+7,u=5*(1e8)+4;
    while(cin>>n)
    {
        t=r=n;
        for(ll i=2; i*i<=t; i++)
        {
            if(t%i==0)
            {
                r-=r/i;
                while(t%i==0)
                {
                    t=t/i;
                }
            }
        }
        if(t>1)
        {
            r-=r/t;
        }
        n=n%m;
        r=r%m;
        cout<<(n*(n+1-r+m)%m*u%m)%m<<'\n';
    }
}

pypy3 解法, 执行用时: 410ms, 内存消耗: 25720K, 提交时间: 2022-04-21 20:52:29

import sys

def phi(n):
    res = n
    i = 2
    while i*i <= n:
        if n % i == 0:
            res -= res // i
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        res -= res // n
    return res

def modProd(x, y):
    return (x % MOD * (y % MOD)) % MOD

MOD = 10 ** 9 + 7
I2 = pow(2, MOD-2, MOD)
for line in sys.stdin:
    n = int(line)
    sm = modProd(n, n+1) * I2
    psm = modProd(n, phi(n)) * I2
    print((sm - psm) % MOD)

C++ 解法, 执行用时: 176ms, 内存消耗: 488K, 提交时间: 2022-01-01 17:03:24

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,r,t,m=1e9+7;
    while(cin>>n){
        t=r=n;
        for(ll i=2; i*i<=t; i++)
            if(t%i==0){
                r-=r/i;
                while(t%i==0)t=t/i;
            }
        if(t>1)r-=r/t;
        cout<<(n%m*(n%m+1-r%m+m)%m*500000004%m)%m<<'\n';
    }
}