[bzoj2818][莫比乌斯反演]Gcd-白红宇

[bzoj2818][莫比乌斯反演]Gcd

阅读量：91 次

发布时间：2019-02-26

本文共 1438 字，大约阅读时间需要 4 分钟。

??????????????????????(x, y)???1 ? x, y ? N?Gcd(x, y)??????????????????????????

????

???????????????????N??????

?????????????????????????????????

???????????p????????????????????

??M = floor(N / p)?

????Gcd(a, b) = 1????????a?b?M?????

???????????????????????

????

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
using namespace std;
typedef long long LL;
// ??????
vector
        
          prime; bool is_prime[11000000 + 1]; void sieve() { is_prime[0] = is_prime[1] = false; for (int i = 2; i <= 11000000; ++i) { if (is_prime[i]) { prime.push_back(i); } for (int j = i; j <= 11000000; j += i) { is_prime[j] = false; } } } // ????????mu int mu[11000000 + 1]; void mobius_sieve() { mu[1] = 1; for (int i = 2; i <= 11000000; ++i) { if (is_prime[i]) { for (int j = i; j <= 11000000; j += i) { mu[j] *= -1; } int k = i * i; for (int j = k; j <= 11000000; j += k) { mu[j] = 0; } } } } int main() { int N; scanf("%d", &N); sieve(); mobius_sieve(); LL ans = 0; for (int p : prime) { if (p > N) break; int M = N / p; if (M == 0) continue; LL sum = 0; for (int d = 1; d <= M; ++d) { if (mu[d] == 0) continue; int k = M / d; sum += mu[d] * (k * k); } ans += sum; } printf("%lld\n", ans); return 0; }