luoguP1390 公约数的和 数学推导_双倍经验

Code:

#include <bits/stdc++.h>
#include <tr1/unordered_map>

#define setIO(s) freopen(s".in","r",stdin)
#define ll long long 
#define ull unsigned long long 
#define maxn 3000000
#define mod 1000000007 
#define inv 500000004
 
using namespace std;
using namespace tr1;
int vis[maxn],prime[maxn],tot; 
ll phi[maxn]; 
unordered_map<ll,ull>ansphi;
void init(){
    phi[1] = 1; 
    for(int i=2;i<maxn; ++i) {
        if(!vis[i]) prime[++tot]=i,phi[i] = i-1; 
        for(int j=1;j<=tot&&i*prime[j]<maxn;++j) {
            vis[i*prime[j]]=1;
            if(i%prime[j]!=0) phi[i*prime[j]]=phi[i]*(prime[j]-1); 
            else {
                phi[i*prime[j]]=phi[i]*(prime[j]);
                break; 
            }
        }
    }    
    for(int i=1;i<maxn;++i) phi[i]+=phi[i-1]; 
}
ll solve(int n){ return phi[n]; }
int main(){
    //setIO("input"); 
    init(); 
    ll n,ans=0,ans1;           
    scanf("%lld",&n);
    for(ll l=1,r;l<=n;l=r+1){                        
        r=(n/(n/l)); 
        ans+=(n/l)*(n/l)*(solve(r)-solve(l-1));       
    }
    ans -= (n+1)*n/2; 
    ans/=2; 
    printf("%lld",ans); 
    return 0; 
}