http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3647
大致题意:
给出一个n*m的长方形,求三个点都在这个长方形的格点上的三角形有多少个。
大致思路:
参考的网上的想法,首先先求出单纯的取三个点,能有多少种求法,再减去三点共线的错误方案数。
计算错误的方案数要分两步
1,要统计不在同一行或者同一列的三点共线,这里使用的方法的是,枚举这个长方形里面的长方形区域,认为两个点的位置在长方形两个对顶的脚上,再在这两个点之间选出第三个点即可。
3,统计在同一行或者同一列上的三点共线的情况。
#include<iostream>
#include<cstdlib>
#include<stdio.h>
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
long long cal(int b)
{
long long a=(long long)b;
if(a<3)return 0;
long long res=((a-2)*(a-1)*a);
res/=6;
return res;
}
int main()
{
int n,m,i,j;
while(cin>>n>>m)
{
long long ans=cal((n+1)*(m+1));
for(i=2;i<=n;i++)
{
for(j=2;j<=m;j++)
{
long long tmp=(gcd(i,j)-1)*(n+1-i)*(m+1-j)*2;
ans-=tmp;
}
}
ans-=cal(n+1)*(m+1);
ans-=cal(m+1)*(n+1);
cout<<ans<<endl;
}
return 0;
}
分享到:
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 1610 Count the Colors.md
acm中zoj1002的可运行C++程序
zoj 1255 The Path.md
包含了zoj700多道题目的源代码,在做题时可以参考
zoj 1810 The Gourmet Club.md
zoj 2499 The Happy Worm.md
zoj 2151 The Highest Profits.md
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
ZOJ1805代码
The reason is that when the director chooses the words from the dictionary and encrypts them, he never changes their order (the words in the dictionary are lexicographically sorted). String a1a2 ... ...
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复