Description

栋栋有一块长方形的地, 他在地上种了一种能量植物, 这种植物可以采集太阳光的能量. 在这些植物采集能量后, 栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起. 栋栋的植物种得非常整齐, 一共有 \(n\) 列, 每列有 \(m\) 棵, 植物的横竖间距都一样, 因此 对于每一棵植物, 栋栋可以用一个坐标 \((x, y)\) 来表示, 其中 \(x\) 的范围是 \(1\) 至 \(n\), 表示是在第 \(x\) 列,\(y\) 的范围是 \(1\) 至 \(m\), 表示是在第 \(x\) 列的第 \(y\) 棵. 由于 能量汇集机器较大, 不便移动, 栋栋将它放在了一个角上, 坐标正好是 \((0, 0)\). 能量 汇集机器在汇集的过程中有一定的能量损失. 如果一棵植物与能量汇集机器连接而成的线段 上有 \(k\) 棵植物, 则能量的损失为 \(2k + 1\). 例如, 当能量汇集机器收集坐标为 \((2, 4)\) 的植物时, 由于连接线段上存在一棵植物 \((1, 2)\), 会产生 \(3\) 的能量损失. 注意, 如果 一棵植物与能量汇集机器连接的线段上没有植物, 则能量损失为 \(1\). 现在要计算总的能量损失. 下面给出了一个能量采集的例子, 其中 \(n = 5, m = 4\), 一共有 \(20\) 棵植物, 在每棵植物上标明了能量汇集机器收集它的能量时产生的能量损失. 在这个例子中, 总共产生 了 \(36\) 的能量损失.

Input

仅包含一行, 为两个整数 \(n\) 和 \(m\).

Output

仅包含一个整数, 表示总共产生的能量损失.

Sample Input

5 4

Sample Output

36

Data Range

对于 10% 的数据:\(1 \leq n, m \leq 10\);

对于 50% 的数据:\(1 \leq n, m \leq 100\);

对于 80% 的数据:\(1 \leq n, m \leq 1000\);

对于 90% 的数据:\(1 \leq n, m \leq 10^4\);

对于 100% 的数据:\(1 \leq n, m \leq 10^5\).

Explanation

这道题一看就是数论都不对~ 然后不会做 QwQ

首先 \(O(n^3)\) 的做法很好想, 直接每个点不停打标记标号就可以了, 然后直接骗到 50 分.

然后突然发现, 每个点的 \(k\) 不就是 \(gcd(n, m)\) 么...... 所以预处理出来就是接近 \(O(n^2 \log n)\) 的做法了, 然后就妥妥骗到 80 分...... =w=

当然如果是在 NOI 赛场上我就不会往下去想了 (我能不能去 NOI 赛场到现在还是个未知数), 但是这是 hustoj, 是要 100% 的数据的, 于是只能膜题解了:

原文地址:http://blog.csdn.net/Clove_unique/article/details/51089272

\[\sum_{i=1}^{n} \sum_{j=1}^{m} (2 \times gcd(i, j) - 1) = 2 \times \sum_{i=1}^{n} \sum_{j=1}^{m} gcd(i, j) - n \cdot m\]

那么我们就可以直接求右边那个看起来十分整齐的式子了, 具体如下 (我不会):

\[\sum_{i=1}^{n} \sum_{j=1}^{m} gcd(i, j)\]

\[ = \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d | gcd(i, j)} \phi(d)\]

\[ = \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d=1}^{n} [d | i] [d | j] \phi(d)\]

\[ = \sum_{d=1}^{n} \sum_{i=1}^{n} [d | i] \sum_{j=1}^{m} [d | j] \phi(d)\]

\[ = \sum_{d=1}^{n} \lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \phi(d)\]

可以用分块来求.

需要预处理 \(\phi\) 的前缀和.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 100100;

lli n, m;
lli vis[maxn], primes[maxn], phi[maxn];

int main(int argc, char** argv)
{
    scanf("%lld%lld", &n, &m);
    if (n > m)
        swap(n, m);
    // At this breakpoint we generate the phi function results.
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            primes[++primes[0]] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= primes[0] && i * primes[j] <= n; j++) {
            lli dup = i * primes[j];
            vis[dup] = 1;
            if (i % primes[j] == 0) {
                phi[dup] = phi[i] * primes[j];
                break;
            } else {
                phi[dup] = phi[i] * (primes[j] - 1);
            }
        }
        phi[i] += phi[i - 1];
    }
    // Finished generation of phi functions.
    // Applying calculations to this problem.
    lli res = 0;
    for (lli i = 1, j; i <= n; i = j + 1) {
        j = min(n / (n / i), m / (m / i));
        res += (lli)(phi[j] - phi[i - 1]) * (n / i) * (m / i);
    }
    res = res * 2 - n * m;
    printf("%lld\n", res);
    return 0;
}