[CQOI2014]数三角形(容斥原理 + 组合计数)
创始人
2025-05-31 21:11:02
0次
[CQOI2014]数三角形 (nowcoder.com)
来源：牛客网
给定一个n x m的网格，请计算三点都在格点上的三角形共有多少个。
下图为4x4的网格上的一个三角形。
注意三角形的三点不能共线。
输入描述:
输入一行，包含两个空格分隔的正整数m和n。
输出描述:
输出一个正整数，为所求三角形数量。
示例1
输入
复制2 2
2 2
输出
复制76
76
说明
数据范围 1<=m,n<=1000
思路：首先我们可以知道n*m矩阵是有(n+1)*(m+1)个点，所以可以这样计算，首先算出来任取三点的个数，然后减去三点共线的个数即可。
三点共线的情况是有2种：
1：与x轴平行或垂直 他的个数可以是每条线上任选3点的 个数，即 C(n+1,3)*(m+1)+C(m+1,3)*(n+1).
2:斜着：假设该斜线可以用y=kx+b表示，k可能大于0，也有可能小于0，其实只需要统一算出大于0的个数然后乘2就行了，对于计算k>0的：我们可以先找到一个直角边为i,j的直角三角形，然后其斜边上的两个端点为两个所需要的点，第三点上这斜线上除了端点还存在的格点上找，数量为gcd(i,j)-1,然后像这样的线段可以平移得到的有（n-i）*(m-j)种，因为正负两种所以乘2 。然后对所有的进行求和就行
最后用res - 1的情况数量 - 2的情况的数量。
描述一下上面为什么是gcd(i,j)-1。
根据这个图：
h=6,l=6 ，斜线总覆盖点为gcd(6,6)+1个点，对于不同长度线段（两个端点在整点上）都对应到一个长或高不同的直角三角形，对于定长的线段我们可以通过将两个点固定在线段的两个端点，另一个点从中间的点中选来得到，方案数就为gcd(h,l)-1。
AC代码:
#include
using namespace std;
#define int long long
int C(int x,int y){return x*(x-1)*(x-2)/6;
}
signed main(){int n,m;cin>>n>>m;int num=(n+1)*(m+1);int ans=C(num,3);ans-=C(n+1,3)*(m+1);ans-=C(m+1,3)*(n+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ans-=(__gcd(i,j)-1)*(n+1-i)*(m+1-j)*2;}}cout< 相关内容
热门资讯
国家电网出“王炸”！4万亿元“...
图源：国家电网官网本报（chinatimes.net.cn）记者李未来 北京报道变压器热度未消，国家...
死磕8年，烧光400亿，中国芯...
来源丨市值榜撰文丨相青2016年，是朱一明的高光时刻。他创办的兆易创新成功登陆A股，打破了国外在NO...
超60万人的体面
2026年伊始，北京通州的一个住宅小区里，裴云涛正带着他的“小兄弟”穿梭在楼宇间。那是一个无人快递车...
贾国龙凭什么 | Findme...
我之所以说彼得蒂尔值得研究，这里就看出来了，他这套观念可以解释很多现代社会问题，比如贾国龙的事情，拿...
在散漫与努力中挣扎的我：如何找...
当我看到“在散漫与努力挣扎的我”这个标题时，心中不由得一阵恍惚。似乎在瞬间，我意识到自己是一个缺乏规...
当AI颠覆了广告收入，该靠什么...
本文来自微信公众号：一鸣的AI交易思考，作者：刘宇轩，原文标题：《当ChatGPT陷入“数据混乱”：...
中国金茂逆势破局：全年销售额超...
本文来源：时代周报 作者：张扬回顾2025年，房地产市场延续筑底态势，多数房企销售规模在低位区间运行...
委托加工≠贴牌！关键看谁真正担...
在健康食品、化妆品、母婴用品等关乎安全与功效的消费领域，“品牌出品”四个字常被默认为品质保证。但事实...
西贝断腕，102家门店关闭背后...
新消费导读2026年1月15日，西贝餐饮创始人贾国龙在朋友圈确认将一次性关闭全国102家门店，约占其...
没有产能却揽下宁德时代1200...
本报（chinatimes.net.cn）记者胡雅文 北京报道近日，宁波容百新能源科技股份有限公司（...