1310. 数三角形

知识点：(a, b)与(c, d)两点连线上点的个数为:gcd(x, y) + 1(包括端点)

（设横坐标差的绝对值为x， 纵坐标差的绝对值为y ）

思路：先算出选三个点的所有情况，再减去三点共线的情况

共线的斜率为0时特判

当共线的斜率大于0时枚举共线的长和宽，设为a、b，则这条线左下角的选法有(n+1-a)*(m+1-b)种

对于每一种选法，左下角看作第一个点，右上角看作第二个点两点中间的点数就是选法个数，即gcd(a, b) - 1。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;ll C(int a)
{if(a < 3)return 0;ll res = (ll)a * (a - 1) * (a - 2) / 6;return res;
}int main()
{IOSint n, m;cin >> n >> m;n ++, m ++;ll ans = C(n * m) - m * C(n) - n * C(m);n --, m --;for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){ll res = (n + 1 - i) * (m + 1 - j) * (__gcd(i, j) - 1);ans -= res * 2;}}cout << ans;return 0;
}

 

1310. 数三角形 - AcWing题库