POJ 3090 Visible Lattice Points （ZOJ 2777)

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 3090 Visible Lattice Points （ZOJ 2777)

最新文章

热门文章