http://exam.upc.edu.cn/problem.php?id=3843&csrf=8oK86t2oHSgi3Q4SX3qOJGeENe6pfXri
時間限制: 1 Sec 內存限制: 128 MB
題目描述
給定一個nxm的網格，請計算三點都在格點上的三角形共有多少個。下圖為4x4的網格上的一個三角形。
注意：三角形的三點不能共線。n×m的網格共有(n+1)×(m+1)個格點。
輸入
輸入一行，包含兩個空格分隔的正整數m和n（1<=m,n<=1000）。
輸出
輸出一個正整數，為所求三角形數量。
樣例輸入
2 2
樣例輸出
76

取補集的思想，三角形的數量等于任取三點的情況減去三點共線的情況

#define FILE() freopen("../../in.txt","r",stdin) #include <bits/stdc++.h>using namespace std;typedef long long ll;ll combine(int n) { //n個點取3個ll m=n,res=1;for(int i=0; i<3; i++) {if(m%3==0) {res*=m/3;} else res*=m;m--;}return res/2; }int gcd(int a,int b){return b?gcd(b,a%b):a; }int main() { // FILE();int n,m;cin>>n>>m;ll ans = combine((n+1)*(m+1))-(n+1)*combine(m+1)-(m+1)*combine(n+1); //先減去橫豎格線上三點共線的for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) { //類似向量，從(0,0)到(i,j)作一線段 gcd(i,j)+1為線段上格點的數量ans-=(gcd(i,j)-1)*(n-i+1)*(m-j+1)*2; //乘2是因為沿y軸翻轉情況一樣}}cout<<ans<<endl;return 0; }

轉載于:https://www.cnblogs.com/NeilThang/p/9356628.html

總結

以上是生活随笔為你收集整理的【组合取补集】数三角形 @CQOI2014/BZOJ3505/upcexam3843的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。