题意描述

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

栋栋的植物种得非常整齐,一共有$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