本文共 1155 字，大约阅读时间需要 3 分钟。
题解：设p为素数 ，则gcd(x/p,y/p)=1也就是说求 x／p以及 y／p的欧拉函数。欧拉筛+前缀和就可以解决
#include #include #include #include #include #include #include #include #include #include #include //#include //CLOCKS_PER_SEC#define se second#define fi first#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define Pii pair #define Pli pair #define ull unsigned long long#define pb push_back#define fio ios::sync_with_stdio(false);cin.tie(0)const int N=1e7+10;const ull base=163;const int INF=0x3f3f3f3f;using namespace std;bool ispri[N];ll pri[N],phi[N];int tot=0;void getphi(int x){ memset(ispri,1,sizeof(ispri)); ispri[1]=false; phi[1]=1; for(int i=2;i<=x;i++) { if(ispri[i]) { pri[++tot]=i; phi[i]=i-1; } for(int j=1;j<=tot&&i*pri[j]<=x;j++) { ispri[i*pri[j]]=false; if(i%pri[j]==0) { phi[i*pri[j]]=phi[i]*pri[j]; break; } phi[i*pri[j]]=phi[i]*(pri[j]-1); } }}ll sum[N];int main(){ int n; cin>>n; getphi(n); ll ans=0; for(int i=1;i<=n;i++)sum[i]=phi[i]+sum[i-1]; for(int i=1;i<=tot;++i){ ans+=sum[n/pri[i]]*2-1; } cout< <
转载于:https://www.cnblogs.com/Mrleon/p/9097806.html