【CQOI2014】数三角形

2019-11-06 07:30:58

字体：大中小

来源：转载

供稿：网友

Description

这里写图片描述

Solution

这题是一个很水的题目，但是一开始就往较难想的地方想，结果细节搞不出来。很明显的正难则反。那么现在的问题就是求三点共线的数量总数。很明显要枚举类似斜率的东西，然后考虑这条线过多少个点，然后算。但是会发现这样算起来非常的麻烦。所以我们考虑先固定两个点，然后求这两个点中间的点的个数，最后再求出这个图中可以放多少条这样的线。枚举这条线在x轴和y轴上的射影，然后gcd+1就是两点之间点的数量。

Code

#include<iostream>#include<stdio.h>#include<string.h>#include<math.h>#include<algorithm>#define fo(i,a,b) for(i=a;i<=b;i++)using namespace std;typedef long long ll;ll i,j,k,l,t,n,m,ans,num,ans1,x,y;int gcd(int x,int y){ int o=1; while(o){ o=x%y; x=y,y=o; } return x;}ll suan(ll x){return x*(x-1)/2*(x-2)/3;}int main(){// freopen("fan.in","r",stdin); scanf("%d%d",&n,&m);++n,++m;num=n*m; ans=num*(num-1)/2*(num-2)/3; fo(i,1,n){ fo(j,1,m){ t=gcd(i,j)+1; ans1+=(n-i)*(m-j)*(t-2)*2; } } ans1+=n*suan(m)+m*suan(n); PRintf("%lld/n",ans-ans1);}

上一篇：LeetCode 3. Longest Substring Without Repeating Characters

下一篇：IO流_数据操作流、内存操作流、打印流、标准输入输出流、随机访问流、合并流、序列化流、Properties、总结