bzoj2005: [Noi2010]能量采集

莫比乌斯反演

题目链接

bzoj2005: [Noi2010]能量采集

题解

对于挡住i,j的点数显然是gcd(i,j)
那么就是求
$2 \times \sum_i^n \sum_j^m gcd(i,j) -n \times m$
枚举带约数$p$
令
$ans=\sum_{p=1}^{n}p*\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=p]$
$ans=\sum_{p=1}^{n}p*\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[gcd(i,j)=1]$
$ans=\sum_{p=1}^{n}p*\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d|i}\sum_{d|j}\mu(d)$
枚举约数d
$ans=\sum_{p=1}^{n}p*\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor$
复杂度$O(n\sqrt{n})$

代码

#include<cstdio> 
#include<algorithm> 
inline int read() {
    int x = 0,f = 1;
    char c = getchar(); 
    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar(); } 
    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar(); 
    return x * f; 
} 
#define int long long 
const int maxn = 100007;
int n,m,mu[maxn],prime[maxn],num;bool p[maxn];  
void get_mu() { 
    mu[1] = 1; int k = maxn - 7;
    for(int i = 2;i <= k;++ i) {
        if(!p[i]) mu[i] = -1,prime[++ num] = i;
        for(int j = 1;j <= num && prime[j] * i <= k;++ j) {
            p[prime[j] * i] = 1; 
            if(i % prime[j] == 0) break; 
            mu[prime[j] * i] = mu[i] * -1;      
        } 
        mu[i] += mu[i - 1]; 
    }   
} 
inline int calc(int x) { 
    int a = n / x ,b = m / x,ret = 0; 
    for(int i = 1,last;i <= a;i = last + 1) { 
        last = std::min(a / (a / i),b / (b / i)); 
        ret += (mu[last] - mu[i - 1]) * (a / i) * (b / i); 
    } 
    return ret; 
}
main() { 
    get_mu(); 
    n = read(),m = read(); 
    if(n > m) std::swap(n,m); 
    int ans = 0;    
    for(int i = 1;i <= n;++ i) ans += 2 * i * calc(i); 
    printf("%lld\n",ans - n * m); 
        return 0;   
}