[BZOJ 2005][Noi2010] 能量采集 容斥

传送门·Teleport!

题目大意

有一个N*M的网格,坐标为(1,1)/(1,2)….(N*M)
每个格点会向(0,0)用光束传输能量,光束上每出现一个格点,就会损失一点能量。
问总共损失的能量数量。

解题报告

老样子,博客附赠样例！

Input:
667 998
Output:
4957744

可以发现一个性质，那就是(x,y)的贡献为gcd(x,y) 原因:

x和y可以每次减去x/gcd(x,y)和y/gcd(x,y)来得到一个可以阻塞(x,y)的点并且此时(x/gcd(x,y),y/gcd(x,y))仍然是整数点
此时应为除数gcd(x,y)为最大的可能除数,所以每次减去的数字是最小化的,所以不存在更多的点能阻塞(x,y)

然而暴力枚举x,y然后gcd的话会T 还用你说!
因为gcd(x,y) < min(n, m),换个角度考虑gcd(x,y)每个数值的出现次数。
设f(i)为最大公因子为i的数对对数
那么i从大往小处理,有以下递推式:
$$ f(i) = \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor – \sum_{j=2}^{ij \leq u} f(i\times j) |u=\max\{n, m\} $$
这显然成立。
复杂度是O(nlogn)的，证明嘛…就是调和级数。
下面给喂代码!

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
typedef long long LL;
int f[110000];
int main () {
    int n, m, u;
    scanf("%d%d", &n, &m);
    u = std :: max(n, m);
    for(int i = u; i; i--) {
        f[i] = (n/i)*(m/i);
        for(int j = 2; i*j<=u; j++)
            f[i] -= f[i*j];
    }
    LL ans = (LL)n*(LL)m;
    for(int i = 2; i<=u; i++)
        ans += (LL)2*(i-1)*(LL)f[i];
    std :: cout << ans;
}