题意描述

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

栋栋的植物种得非常整齐，一共有$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$棵植物，在每棵植物上标明了能量汇集机器收集它的能量时产生的能量损失。

2608.png

在这个例子中，总共产生了$36$的能量损失。

输入格式

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

输出格式

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

Input & Output ‘s examples

Input ‘s eg 1

5 4

Output ‘s eg 1

36

Input ‘s eg 2

3 4

Output ‘s eg 2

20

数据范围和约定

对于$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)$，其与原点连线后经过的点的数量为

因此，题目可以转化为求出

化简一下，也就是求出

之后采用$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;
}

THE END