【洛谷 P1390】公约数的和（欧拉函数）

题目链接

做过\(n\)遍这种题了。。。

答案就是\(\sum_{i=1}^{n}\sum_{j=1}^{n/i}[\varphi(j)*i]\)

线筛欧拉函数求前缀和直接算就行。

#include <cstdio>

const int MAXN = 2000010;

int v[MAXN], prime[MAXN], cnt, n;

long long ans, phi[MAXN];

int main(){

    scanf("%d", &n);

    phi[1] = 1;

    for(int i = 1; i <= n; ++i){

       if(!v[i]){

         v[i] = i;

         prime[++cnt] = i;

         phi[i] = i - 1;

       }

       for(int j = 1; j <= cnt; ++j){

          if(prime[j] > v[i] || prime[j] * i > n) break;

          v[i * prime[j]] = v[i];

          phi[i * prime[j]] = phi[i] * (i % prime[j] ? prime[j] - 1 : prime[j]);

       }

    }

    for(int i = 2; i <= n; ++i) phi[i] += phi[i - 1];

    for(int i = 1; i <= n; ++i)

       ans += phi[n / i] * i;

    printf("%lld\n", ans);

    return 0;

}

巴特西

【洛谷 P1390】公约数的和（欧拉函数）

最新文章

热门文章

巴特西

【洛谷 P1390】 公约数的和 （欧拉函数）

最新文章

热门文章

【洛谷 P1390】公约数的和（欧拉函数）