BZOJ 2005 能量采集

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36402

题意：在一块长方形的地上，种了一种能量植物，植物种得非常整齐，一共有n列，每列有m棵，每个植物对应一个坐标(x, y)。在(0, 0)处有一个能量收集器，每个植物到能量收集器都有能量损失，如果一棵植物与能量汇集机器连接而成的线段上有k棵植物，则能量的损失为2k + 1，如果一棵植物与能量汇集机器连接的线段上没有植物，则能量损失为1。求总能量损失。

思路：令f[d]为(x, y) = d的对数，那么答案就是sigma(f[i]*((i-1)*2+1))。分两步来理解这个结论，if gcd(x1, y1) = gcd(x2, y2)那么他们的能量损失一样多（与能量汇集机器连接而成的线段上的植物一样多），再来看看具体的能量损失（也就是如何判断连接线段上的植物有多少棵），那么显然与gcd的值有关，结果就是2 * gcd - 1。

code：

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAXN = 100005;
LL f[MAXN];    // f[i]表示满足gcd(x, y) = i (1 <= x <= n, 1 <= y <= m)的对数

int main()
{
    LL n, m;
    while (scanf("%lld %lld", &n, &m) != EOF) {
        if (n > m) swap(n, m);
        LL ans = 0;
        for (int i = n; i >= 1; --i) {
            f[i] = (n / i) * (m / i);
            for (int j = i + i; j <= n; j += i) {
                f[i] -= f[j];
            }
            ans += f[i] * (2 * i - 1);    // 所有gcd(x, y) = i，产生的能量损失就算出来了
        }
        printf("%lld
", ans);
    }
    return 0;
}