题意描述

栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。

栋栋的植物种得非常整齐，一共有 $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$ 的能量损失。

输入格式

输入仅包含一行，为两个整数 $n$ 和 $m$ 。

输出格式

输出仅包含一个整数，表示总***生的能量损失。

Input & Output 's examples

Input 's eg 1

5 4

Output 's eg 1

Input 's eg 2

3 4

Output 's eg 2

数据范围和约定

对于 $10\%$ 的数据： $1 ≤ n, m ≤ 10$ ；
对于 $50\%$ 的数据： $1 ≤ n, m ≤ 100$ ；
对于 $80\%$ 的数据： $1 ≤ n, m ≤ 1000$ ；
对于 $90\%$ 的数据： $1 ≤ n, m ≤ 10^4$ ；
对于 $100\%$ 的数据： $1 ≤ n, m ≤ 10^5$ 。

分析

一道比较麻烦的数论题，但应该还没有 $\text{NOI}$ 的难度。

在做这题之前，我们首先要了解一个前置知识：对于平面直角坐标系中的任意一点 $(x , y)$ ，其与原点连线后经过的点的数量为$ $gcd(x , y) - 1$ $

因此，题目可以转化为求出$ $\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 \times m$ $

~~之后采用 $O(n^2)$ 复杂度的暴力求解，可以得到 $80$ 分的好成绩……~~

考虑如何快速求出 $\sum_{i = 1} ^ {n} \sum_{j = 1} ^ {m} gcd(i , j)$ ，显然，这并不好求。

正难则补，考虑容斥，设 $cnt[i]$ 表示以 $i$ 为公因数(注意不是最大公因数)的点对个数，则 $cnt[i] = \lfloor \frac{n}{i} \rfloor \times \lfloor \frac{m}{i} \rfloor$

之后减去以 $2i , 3i , 4i…j * i (j \leq \lfloor \frac{n}{i}\rfloor)$ 作为公约数的部分，最后留下的就是以 $gcd(i , j)$ 为公因数的点对数目。

时间复杂度为 $O(n \log n)$ ，比莫反稍慢一点，但也足以通过本题。

剩下的见代码即可。

Code[80pts]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

ll ans = 0;

ll gcd(ll a , ll b){
    return !b ? a : gcd(b , a % b);
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    ll n , m; scanf("%lld%lld" , &n , &m);
    rep(i , 1 , n){
        rep(j , 1 , m){
            ans += 2 * gcd(i , j) - 1;
        }
    }
    printf("%d\n" , ans);

    return 0;
}

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

ll cnt[M] , ans = 0;

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    ll n , m; scanf("%lld%lld" , &n , &m);
    ll maxn = max(n , m);
    rep(i , 1 , maxn){
        cnt[i] = (ll)(n / i) * (ll)(m / i);
    }
    per(i , maxn , 1){
        for(ll j = 2 * i; j <= maxn; j += i) cnt[i] -= cnt[j];
    }
    rep(i , 1 , maxn){
        ans += (ll)i * cnt[i];
    }
    ans *= 2; ans -= n * m;
    printf("%lld\n" , ans);

    return 0;
}

【NOI2010】能量采集-题解