洛谷P3166：https://www.luogu.org/problemnew/show/P3166
思路
用组合数求出所有的3个点组合（包含不合法的）
把横竖的3个点共线的去掉
把斜的3个点共线的去掉（枚举所有的矩阵把每个矩阵的对角线去掉）
每一条对角线可以取得首尾两点有(n-i)*(m-j)*2种方式可以选择
每一条对角线除了首尾两个点之外可以取到中间点有gcd(i,j)-1个 因此有对于每个条对角线有gcd(i,j)-1种要去掉（相似三角形）
代码
#include<iostream>
using namespace std;
#define maxn 1010
long long n,m,ans=
1;
long long gcd(
long long a,
long long b)
{
if(!b)
return a;
else return gcd(b,a%
b);
}
long long C(
int n,
int m)
{
long long ret=
1;
for(
int i=
1;i<=m;i++
)
ret=ret*(n-i+
1)/
i;
return ret;
}
int main()
{
cin>>n>>
m;
n+=
1;
m+=
1;
ans=C(n*m,
3);
if(n>=
3) ans-=C(n,
3)*m;
//减去横竖的点
if(m>=
3) ans-=C(m,
3)*
n;
for(
long long i=
1;i<n;i++
)
for(
long long j=
1;j<m;j++
)
ans-=(n-i)*(m-j)*(gcd(i,j)-
1)*
2;
//减去斜的点
cout<<
ans;
}
View Code
转载于:https://www.cnblogs.com/BrokenString/p/9693856.html
相关资源：JAVA上百实例源码以及开源项目
