做法:组合数
思路
因为是的网格,所以一共有个点
所以三角形数量为在所有点中任意选取三点中减去三点共线的情况即可不合理的情况分为三种
1.横线
2.竖线
3.斜线
前两种情况很好求,所有横着(竖着)的点中选取三个点乘上竖着(横着)的点数即可
第三种情况我们可以先找到一个直角边为i,j的直角三角形,然后其斜边上的两个端点为两个所需要的点,第三点上这斜线上除了端点还存在的格点上找,数量为。因为斜线存在两种,即斜率为正和斜率为负,因此需要乘2.
代码
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=100010; const int INF=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-6; const double PI=acos(-1.0); ll C(ll n,ll m){ ll ans = 1; for(ll i=1;i<=m;i++){ ans=ans*(n-m+i)/i; } return ans; } void solve(){ ll n,m;cin>>n>>m; ll cnt=(n+1)*(m+1); ll ans=C(cnt,3); ans-=C(n+1,3)*(m+1); ans-=C(m+1,3)*(n+1); rep(i,1,n){ rep(j,1,m){ ans-=(n+1-i)*(m+1-j)*(__gcd(i,j)-1)*2; } } cout<<ans<<"\n"; } int main(){ ios::sync_with_stdio(0);cin.tie(0); // int t;cin>>t;while(t--) solve(); return 0; }