C++(g++ 7.5.0) 解法, 执行用时: 1100ms, 内存消耗: 86460K, 提交时间: 2022-11-03 15:34:52

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), 1
using namespace std;

const int N = 5e6 + 10;

typedef long long LL;

int t, n;
LL cnt, p[N], moi[N], S_moi[N];
bool st[N];
unordered_map<LL, LL> mp_mu;

void init()
{
    moi[1] = 1;
    for(int i = 2; i <= N; i ++)
    {
        if(!st[i]) p[cnt ++] = i, moi[i] = -1;
        for(int j = 0; i * p[j] <= N; j ++)
        {
            st[i * p[j]] = 1;
            if(i % p[j] == 0)
                break;
            moi[i * p[j]] = -moi[i];
        }
    }
    
    for(int i = 1; i <= N; i ++)
        S_moi[i] = S_moi[i - 1] + moi[i];
}

LL Sum_moi(LL x)
{
    if(x <= N) return S_moi[x];
    if(mp_mu[x]) return mp_mu[x];
    
    LL res = 1;
    for(LL l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        res -= Sum_moi(x / l) * (r - l + 1);
    }
    return mp_mu[x] = res; 
}

LL Sum_phi(LL x)
{
    LL res = 0;
    for(LL l = 1, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        res += (Sum_moi(r) - Sum_moi(l - 1)) * (x / l) * (x / l);
    }
    return (res - 1) / 2 + 1;
}

void sovle()
{
    cin >> n;
    cout << Sum_phi(n) << " " << Sum_moi(n) << endl;
}

int main()
{
    IOS;
    init();
    cin >> t;
    while(t --)
        sovle();
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1241ms, 内存消耗: 124428K, 提交时间: 2022-09-04 15:14:22

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e6+10;
int cnt=0,prime[N];
bool vis[N];
int phi[N],mu[N];
ll s1[N],s2[N];
map<ll,ll> f1,f2; 
void init(){
	phi[1]=mu[1]=1;
	s1[1]=s2[1]=1;
	for(int i=2;i<=N-10;i++){
		if(!vis[i]){
			prime[++cnt]=i;
			phi[i]=i-1;mu[i]=-1;
		}
		s1[i]=s1[i-1]+phi[i];
		s2[i]=s2[i-1]+mu[i];
		for(int j=1;j<=cnt&&prime[j]*i<=N;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0){
				mu[i*prime[j]]=0;
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}else{
				mu[i*prime[j]]=-mu[i];
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
		}
	}
}
ll query1(ll n){
	if(n<=N-10) return s1[n];
	if(f1.find(n)!=f1.end()) return f1[n];
	ll ans=n*(n+1)/2;
	for(ll l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ll a=query1(n/l);
		ans-=(r-l+1)*a;
	}
	return f1[n]=ans;
}
ll query2(ll n){
	if(n<=N-10) return s2[n];
	if(f2.find(n)!=f2.end()) return f2[n];
	ll ans=1;
	for(ll l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ll a=query2(n/l);
		ans-=(r-l+1)*a;
	}
	return f2[n]=ans;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	init();
	int T;cin>>T;
	while(T--){
		ll n;cin>>n;
		cout<<query1(n)<<" "<<query2(n)<<endl;
	}
	return 0;
}