C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 412K, 提交时间: 2022-10-13 21:17:45

#include <iostream>
#define int long long
using namespace std;

int phi(int x)
{
    int res=x;
    for(int i = 2; i*i<=x;i++)
    {
        if(x%i==0){
            res=res*(i-1)/i;
            while(!(x%i))
            {
                x/=i;
            } 
        } 
    }
    if(x>1)return res*(x-1)/x;
    return res;
}

signed main()
{
    int x;
    cin >> x;
    int res=phi(x)+x;
    for(int i = 2; i*i <= x; i++)
    {
        if(x%i==0)
        {
            if(i*i==x)
            {
                res+=phi(i)*i;
            }else
            res+=phi(x/i)*i+phi(i)*(x/i);
        }
    }
    cout << res<<endl;
}

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 368K, 提交时间: 2020-03-06 23:26:02

#include<cstdio>
#include<cmath>
#define ll long long
ll n,ans,i;
ll euler(int x)
{
    int res=x;
    for(int i=2; i<=sqrt(x); 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;
}
int main()
{
    while(~scanf("%lld",&n))
    {
        ans=0;
        for(i=1; i<sqrt(n); i++)if(n%i==0)
                ans+=i*euler(n/i)+n/i*euler(i);
        if(i*i==n)ans+=i*euler(i);
        printf("%lld\n",ans);
    }
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 412K, 提交时间: 2023-06-21 23:29:37

#include <bits/stdc++.h>
using namespace std;
long long n,ans=1;
int main(){
    cin >> n;
    long long nn = n;
    for (long long i = 2; i * i <= n; i++) if (n % i == 0) {
        nn /= i;
        int t = 0;
        while (n % i == 0)t++, n /= i;
        ans = ans * (t * (i - 1) + i);
    }
    if (n != 1)nn /= n, ans = ans * (2 * n - 1);
    cout << ans * nn << '\n';
    return 0;
}