题意描述

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

栋栋的植物种得非常整齐，一共有列，每列有棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标来表示，其中的范围是至，表示是在第列，的范围是至，表示是在第列的第棵。

由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是。

能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有棵植物，则能量的损失为。例如，当能量汇集机器收集坐标为的植物时，由于连接线段上存在一棵植物，会产生的能量损失。注意，如果一棵植物与能量汇集机器连接的线段上没有植物，则能量损失为。现在要计算总的能量损失。

下面给出了一个能量采集的例子，其中，，一共有棵植物，在每棵植物上标明了能量汇集机器收集它的能量时产生的能量损失。

在这个例子中，总***生了的能量损失。

输入格式

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

输出格式

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

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

数据范围和约定

对于的数据：；
对于的数据：；
对于的数据：；
对于的数据：；
对于的数据：。

分析

一道比较麻烦的数论题，但应该还没有的难度。

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

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

化简一下，也就是求出$$

之后采用复杂度的暴力求解，可以得到分的好成绩……

考虑如何快速求出，显然，这并不好求。

正难则补，考虑容斥，设表示以为公因数(注意不是最大公因数)的点对个数，则

之后减去以作为公约数的部分，最后留下的就是以为公因数的点对数目。

时间复杂度为，比莫反稍慢一点，但也足以通过本题。

剩下的见代码即可。

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