记录编号	600735	评测结果	AAAAAAAAAA
题目名称	2602.[BZOJ 2818]GCD	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	1.913 s
提交时间	2025-05-12 21:08:52	内存使用	84.80 MiB

#include <iostream> 
#include <vector>
#include <bitset>
using namespace std;
const int N=1e7;
vector<int>v;
bitset<N+7>b;
long long phi[N+7];
int main(){
    int n;
    cin>>n;
    v.push_back(0);
    phi[1]=1;
    for(int i=2;i<=N;i++){
        if(!b[i]){
            v.push_back(i);
            phi[i]=i-1;
        }
        for(int j=1;j<=v.size();j++){
            if(v[j]*(long long)i>N) break;
            b[i*v[j]]=1;
            phi[i*v[j]]=phi[i]*phi[v[j]];
            if(i%v[j]==0){
                phi[i*v[j]]=phi[i]*v[j];
                break;
            }
        }
    }
    for(int i=1;i<=N;i++){
//        cout<<i<<":"<<phi[i]<<endl;
        phi[i]+=phi[i-1];
    }
    long long ans=0;
    for(int i=2;i<=n;i++){
        if(!b[i]){
            ans+=2*phi[n/i]-1;
        }
    }
    cout<<ans;
    return 0;
}