codevs 3693 数三角形

/*
n*m个点中选3个 再排除三点共线
共线分两类
1 在横线或者竖线上 m*C(n,3) n*C(m,3)
2 在对角线上
这个比较麻烦 以为对角线和矩阵是一一对应的
我们转化成求矩阵 并且保证有两个点在矩阵的角上
接下来的问题就是求 n m 大小的矩阵对角线经过几个点
我们设可构成的最小的三角形的底和高分别是ni mi
显然ni mi 分别是n m的约数 那么分成的线段数也是nm的约数
分成的点数是线段数+1 那么点数最多就是gcd了 去掉两头的
所以共有gcd(n m)-1
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1810
#define ll unsigned long long
using namespace std;
ll n,m,t;
int gcd(int a,int b)
{
return !b?a:gcd(b,a%b);
}
ll C(ll a,ll b)
{
if(b>a-b)b=a-b;
ll r=;
for(int i=;i<=b;i++,a--)r=(r*a)/i;
return r;
}
int main()
{
cin>>n>>m;n++,m++;
for(int i=;i<=n-;i++)
for(int j=;j<=m-;j++)
t+=((n--i+)*(m--j+))*(gcd(i,j)-);
t<<=;
if(m>=)t+=m*C(n,);
if(n>=)t+=n*C(m,);
ll tot=C(n*m,);
cout<<tot-t<<endl;
return ;
}
上一篇:20155205 郝博雅 Exp2 后门原理与实践


下一篇:做中学learning by doing——个人感想20155312张竞予