【JZOJ3598】【CQOI2014】数三角形

2019-11-06 06:04:25

字体：大中小

来源：转载

供稿：网友

Mission

这里写图片描述对于100%的数据1<=m,n<=1000 $对于100/%的数据 1<=m,n<=1000$

Solution

鬼题，ans=C3(n∗m)−Ans $ans=C^3_(n*m)-Ans$ ，其中Ans $Ans$ 表示三点共线的数目；枚举最长边的向量(x,y) $(x,y)$ ，容易算出贡献及个数。

Code

#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<math.h>#define ll long longusing namespace std;const char* fin="aP1.in";const char* fout="aP1.out";const ll inf=0x7fffffff;const ll maxn=1007;ll n,m,i,j,k,ans;ll c[maxn*maxn][4];ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}int main(){ scanf("%lld%lld",&n,&m);n++,m++; for (i=0;i<maxn*maxn;i++){ c[i][0]=1; for (j=1;j<=min(i,3LL);j++) c[i][j]=c[i-1][j-1]+c[i-1][j]; } ans=c[n*m][3]; for (i=0;i<n;i++) for (j=0;j<m;j++){ if (i==0 && j==0) continue; else if (i==0) k=j-1; else if (j==0) k=i-1; else k=(gcd(i,j)-1)*2; ans-=(n-i)*(m-j)*k; } PRintf("%lld",ans); return 0;}