【JZOJ3598】【CQOI2014】数三角形

2019-11-06 07:30:52

字体：大中小

来源：转载

供稿：网友

Description

这里写图片描述

Data Constraint

对于30%的数据 1<=m,n<=10

对于100%的数据 1<=m,n<=1000

Solution

这道题其实很水，虽然我考场上打挂了。我们正难则反。ans=在N*M的网格中任意三点的方案数-三点成直线的方案。现在问题成了如何求三点成直线的方案。我们枚举一个长为x,宽为y的矩阵，强制有两点放在该矩阵的左上角和右下角。现在只要求在该矩阵中有多少点在左上角到右下角的直线上。数量显然是gcd(x,y)−1 $gcd(x,y)-1$ 。而在N*M的网格中长为x,宽为y的矩阵的数量为(n+1−x)∗(m+1−y) $(n+1-x)*(m+1-y)$ 。

Code

#include<iostream>#include<cmath>#include<cstring>#include<cstdio>#include<algorithm>#define ll long longusing namespace std;const int maxn=1e6+5;struct code{ int a,b;}b[maxn];ll n,m,i,t,j,k,l,x,y,z,ans,num;ll dg(ll x){ return x*(x-1)*(x-2)/6;}int pan(ll x,ll y){ ll r=x%y; while (r) x=y,y=r,r=x%y; return y;}bool cmp(code x,code y){ return x.b<y.b || x.b==y.b&& x.a<y.a;}int main(){// freopen("data.in","r",stdin); scanf("%lld%lld",&n,&m);n++;m++; t=n*m; ans=dg(t)-n*dg(m)-m*dg(n); for (i=2;i<n;i++) for (j=2;j<m;j++){ t=pan(i,j); if (t<2) continue;t--; ans-=(n-i)*(m-j)*t*2; } PRintf("%lld/n",ans);}

上一篇：萌萌哒的第四题

下一篇：2-SAT入门——UVALive - 3211