トーシェント関数の和
(math/totient_sum.hpp)

#pragma once
#include<map>

/**
 * @brief トーシェント関数の和
 */

template<typename T>
T totient_sum(long long n){
    static std::map<long long,T> m2;
    static bool init=1;
    static long long* m=new long long[10000000]();
    if(init){
        init=0;
        long long k=1e7;
        for(long long i=1;i<=k;i++)m[i]=i;
        for(long long i=1;i<=k;i++)for(long long j=i*2;j<=k;j+=i)m[j]-=m[i];
        for(long long i=1;i<k;i++)m[i+1]+=m[i];
    }
    if(n<1e7)return m[n];
    else if(m2.count(n))return m2[n];
    T ans=T(n)*(n+1)/2;
    long long mx=0;
    for(long long i=1;i*i<n;i++){
        ans-=T(n/i-n/(i+1))*totient_sum<T>(i);
        mx=n/(i+1)+1;
    }
    for(long long i=2;i<mx;i++){
        ans-=totient_sum<T>(n/i);
    }
    return m2[n]=ans;
}

#line 2 "math/totient_sum.hpp"
#include<map>

/**
 * @brief トーシェント関数の和
 */

template<typename T>
T totient_sum(long long n){
    static std::map<long long,T> m2;
    static bool init=1;
    static long long* m=new long long[10000000]();
    if(init){
        init=0;
        long long k=1e7;
        for(long long i=1;i<=k;i++)m[i]=i;
        for(long long i=1;i<=k;i++)for(long long j=i*2;j<=k;j+=i)m[j]-=m[i];
        for(long long i=1;i<k;i++)m[i+1]+=m[i];
    }
    if(n<1e7)return m[n];
    else if(m2.count(n))return m2[n];
    T ans=T(n)*(n+1)/2;
    long long mx=0;
    for(long long i=1;i*i<n;i++){
        ans-=T(n/i-n/(i+1))*totient_sum<T>(i);
        mx=n/(i+1)+1;
    }
    for(long long i=2;i<mx;i++){
        ans-=totient_sum<T>(n/i);
    }
    return m2[n]=ans;
}