http://poj.org/problem?id=3090
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1777
题目大意:
给你一个坐标系和一个范围,求x、y在[0,N]这个范围内,未被挡住点的个数。
被挡住的点定义为:从原点引一条射线到某个点,若之前经过其他的点,则被挡住。
思路:
未被挡住的一定是互质的(由斜率可以想到)
然后直接打表吧。
#include<cstdio>
const int MAXN=1002;
bool vis[MAXN][MAXN]={0};
int gcd(int x,int y)
{
return y==0? x : gcd(y,x%y);
}
int main()
{
for(int i=1;i<=1000;i++)
{
for(int j=1;j<=i;j++)
if(gcd(i,j)==1) //互质一定不会经过
vis[i][j]=true;
}
int T;
scanf("%d",&T);
for(int ri=1;ri<=T;ri++)
{
int n;
scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
if(vis[i][j]==1)
ans++;
}
ans++; //(1,0)的情况
ans<<=1;//ans *=2;我只算半边
ans--;//(1,1)算两次
printf("%d %d %d\n",ri,n,ans);
}
}
分享到:
相关推荐
自动探测POJ、HDU、SOJ、ZOJ水题,对于有志于刷遍各种水题的ACMer来说非常有用
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
poj 2403 Hay Points.md
POJ题解 个人写法 线段树每个人都不一样
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类