题号 NC19934
名称 [CQOI2014]数三角形
来源 [CQOI2014]
每日一题三期汇总贴~


如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：开开心心写
思路：
三角形 = 三点不共线
求三角形个数 = 选择所有三点的方案（好算）- 三点共线的方案（不好算）
三点共线的方案 = 横着共线的方案（好算）+ 竖着共线的方案（好算）+ 斜着共线的方案（不好算）
其中，括号里写着好算的都是简单组合数。

那么现在来画图，在一个（n，m）的矩形之中，什么情况下连接主对角线和副对角线，会发生三点共线的情况？

如图所示，红色箭头标注的线上就会存在三点共线。（注意，这是副对角线，左下、右上）

结论（1）：
在（n，m）矩形之中，主、副对角线存在对称性，所以算一个就好，答案×2
结论（2）：
（n，m）矩形什么情况下，存在主、副对角线中三点共线情况？
gcd(n,m)>1。
可以正面思考：gcd(n,m)>1时，令k=gcd(n,m)，则可知最小的矩形的比例其实为(n/k, m/k)，所以把这个小矩形的对角线一直延长，由相似性可知，既然过了(n,m)，也会过1(n/k, m/k)、2(n/k, m/k)、等等点，这是按比例来的。
可以反面思考：gcd(n,m)=1时，说明(n,m)互斥，互斥的点之中，在(0-n)与(0-m)的序列之中，不可能出现等比例的缩放问题。
结论（3）：
（n，m）矩形当中，怎么去重斜线？
步骤（1）：枚举（n，m）矩形当中的所有的小矩形，即长宽从1-n，1-m来枚举。
步骤（2）：在（n，m）矩形之中，对于固定长宽的小矩形（i，j），这样的小矩形有多少个？
画画图，从左上角（0，0），右下角（i，j）开始。
从左到右，可以从（i，j）平移到（i，m），共有 m+1-j 个
从上到下，可以从（i，j）平移到（n，j），共有 n+1-i 个
所以乘法原理
结论（4）：在（n，m）矩形之中的固定长宽的小矩形（i，j），贡献度是多少？
注意！！！注意！！！这里的坑点很大。因为，我们已经固定了这个小矩形，所以要求这个（i，j）矩形的贡献度，在选共线三点的时候，一定要选择最远的两点和中间的某一点（如果不选最远的两点，那么这个矩形则不是定义中的（i，j）的矩形）。在这个选择中，对角线总点数是 gcd(i,j) + 1，去掉最远两点，剩下可选点是 gcd(i,j)-1 个。

所以，综上所述，问题解决。代码其实没几行。
（吐槽：斜线画直了好难）

#include<bits/stdc++.h>
using namespace std;

int m, n;

long long Cn3(int x){
    return 1LL * x * (x - 1) * (x - 2) / 6;
}

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

int main(){
    scanf("%lld%lld", &m, &n);
    long long ans = Cn3((n+1) * (m+1)) - (m+1) * Cn3(n+1) - (n+1) * Cn3(m+1);
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
                if (gcd(i, j) > 1)
                    ans -= 2 * (gcd(i, j) - 1) * (m + 1 - i) * (n + 1 - j);
    printf("%lld\n", ans);
    return 0; 
}

补充说明：
这个题入手最大的问题其实是：数据样例很小且组数很少。
比如n=m=1时，答案显然为4.
但是，n=1，m=2时，这个答案是多少？怎么做到不重复不遗漏？
n=m=2时，答案为76怎么算的？肯定不是数对吧？思路梳理还是得花心思。
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目5月5日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴