目录

题目-数三角形

在这里插入图片描述

问题分析

因为直接求符合条件的三角形的个数不好求, 因此可以用补集的方法考虑
a n s = S − t ans = S - t ans=S−t, S S S是全集, t t t是非法的方案
在本问题中, 非法的方案是三角形三个点在一条直线的情况, 按照集合的方式分析
直线可以按照斜率不同划分为不同的直线

假设<stron>的行数是 n n n, 列数是 m m m</stron>

  • 斜率为 0 0 0, 方案数 n ⋅ C m 3 n \cdot C_m ^ 3 n⋅Cm3​
  • 斜率是 + ∞ + \infty +∞, 方案数 m ⋅ C n 3 m \cdot C_n ^ 3 m⋅Cn3​
  • 斜率 > 0 > 0 >0
  • 斜率 < 0 < 0 <0

对于斜率 < 0 < 0 <0的情况, 与斜率 > 0 > 0 >0的情况是对称的, 因此只需要考虑斜率 > 0 > 0 >0的情况

对于斜率 > 0 > 0 >0的直线, 继续对该问题进行划分, 将所有斜率 > 0 > 0 >0的三个点构成的直线按照最高点和最低点横纵坐标之差进行分类

具体情况如下
在这里插入图片描述

最高点和最低点横坐标之差是 i i i, 纵坐标之差是 j j j的所有情况
在这里插入图片描述对于直线上任意一点 ( x , y ) (x, y) (x,y), 都有 y − j x − i = b − j a − i \frac{y - j}{x - i} = \frac{b - j}{a - i} x−iy−j​=a−ib−j​
那么直线方程有
y = b − j a − i ⋅ ( x − i ) + j y = \frac{b - j}{a - i} \cdot (x - i) + j y=a−ib−j​⋅(x−i)+j
假设 gcd ⁡ ( a − i , b − j ) = t \gcd(a - i, b - j) =t gcd(a−i,b−j)=t
直线方程可以写成
y = b − j t a − i t ⋅ ( x − i ) + j y = \frac{\frac{b - j}{t}}{\frac{a - i}{t}} \cdot (x - i) + j y=ta−i​tb−j​​⋅(x−i)+j
对方程进行变换
y = b − j t ⋅ x − i a − i t + j y = \frac{b - j}{t} \cdot \frac{x - i}{\frac{a - i}{t}} + j y=tb−j​⋅ta−i​x−i​+j
因为 b − j t \frac{b - j}{t} tb−j​与 a − i t \frac{a - i}{t} ta−i​互质, 因此 y ∈ Z + y \in Z ^ + y∈Z+等价于
a − i t    ∣    ( x − i ) \frac{a - i}{t} \; | \; (x- i) ta−i​∣(x−i)

因为 i ≤ x ≤ a i \le x \le a i≤x≤a, 因此
i ≤ q ⋅ a − i t + i ≤ a i \le q \cdot \frac{a - i}{t} + i \le a i≤q⋅ta−i​+i≤a

推导的得出
0 ≤ q ≤ t 0 \le q \le t 0≤q≤t

也就是说 0 ≤ q ≤ gcd ⁡ ( a − i , b − j ) 0 \le q \le \gcd(a - i, b - j) 0≤q≤gcd(a−i,b−j), 假设能取到直线上的所有点, 总的点的数量是 gcd ⁡ ( a − i , b − j ) + 1 \gcd(a - i, b - j) + 1 gcd(a−i,b−j)+1

但是在直线中不能取到直线的两个端点, 因此中间的点的数量是
gcd ⁡ ( a − i , b − j ) − 1 \gcd(a - i, b - j) - 1 gcd(a−i,b−j)−1

也就是说, 斜率为正数的直线数量是
∑ 1 ≤ i ≤ n , 1 ≤ j ≤ m ( n − i ) ( m − j ) ( gcd ⁡ ( i , j ) − 1 ) \sum _{1 \le i \le n, 1 \le j \le m}(n - i)(m - j)(\gcd (i, j) - 1) 1≤i≤n,1≤j≤m∑​(n−i)(m−j)(gcd(i,j)−1)
斜率为负数的情况也是一样的

斜率为非 0 0 0并且非 ∞ \infty ∞的直线的数量是
2 × ∑ 1 ≤ i ≤ n , 1 ≤ j ≤ m ( n − i ) ( m − j ) ( gcd ⁡ ( i , j ) − 1 ) 2 \times \sum _{1 \le i \le n, 1 \le j \le m}(n - i)(m - j)(\gcd (i, j) - 1) 2×1≤i≤n,1≤j≤m∑​(n−i)(m−j)(gcd(i,j)−1)

算法步骤

  • 计算斜率为 0 0 0和 + ∞ + \infty +∞的情况, 也就是求组合数
  • 计算斜率为正数的情况
  • 计算斜率为负数情况
  • 计算全集 S S S, 减去所有非法情况就是合法的三角形数量

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1010;

int n, m;

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

LL C(LL a) {
   
    return (LL) a * (a - 1) * (a - 2) / 6;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> m >> n;
    n++, m++;

    LL ans = C(n * m) - n * C(m) - m * C(n);
    for (int i = 1; i <= n; ++i) {
   
        for (int j = 1; j <= m; ++j) {
   
            LL val = 2 * (n - i) * (m - j) * (gcd(i, j) - 1);
            ans -= val;
        }
    }

    cout << ans << '\n';

    return 0;
}