题解 P1390 【公约数的和】

cz666 · 2019-04-09 16:11:56 · 题解

欧拉函数可以卡过此题（亲身尝试过了，开O2刚刚好卡过：AC的测评记录）。

直接贴代码吧，这道题有好多倍经验呢...（开心开心...）

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2000003;
int a[maxn+1],b[maxn+1],v[maxn+1];
int sz,n,p[maxn+1],fi[maxn+1];
inline void Eular(){//用素数互质关系来寻找欧拉函数
    for(register int i=2;i<=maxn;i++){
        if(!v[i]) p[++sz]=i,fi[i]=i-1;
        for(register int j=1;j<=sz && p[j]*i<=maxn;j++){
            v[p[j]*i]=1;
            if(i%p[j]==0){fi[i*p[j]]=fi[i]*p[j];break;}
            fi[i*p[j]]=fi[i]*(p[j]-1);
        }
    }
} 
//超级像欧拉筛，不错，时间复杂度和欧拉筛的确相等，只是收集答案公式不一样而已。
signed main(){
    v[1]=1;Eular();//预处理以1~maxn作为基数的所有欧拉函数值
    for(register int i=1;i<=maxn;i++)
     for(register int j=i*2;j<=maxn;j+=i) a[j]+=i*fi[j/i];
    for(register int i=1;i<=maxn;i++) b[i]=b[i-1]+a[i];
    scanf("%lld",&n);
    printf("%lld\n", b[n]);
    //O(1)回答此题的所有问题 
    return 0;
}

但是不开O2会被卡掉4个点 QAQ 。