POJ3090 Visible Lattice Points 欧拉筛

题目大意：给出范围为(0, 0)到(n, n)的整点，你站在原点处，问有多少个整点可见。

线y=x和坐标轴上的点都被(1,0)(0,1)(1,1)挡住了。除这三个钉子外，如果一个点(x,y)不互质，则它就会被点(x0, y0) （x0,y0互质，x/x0==y/y0）挡住。能看见的钉子关于线y=x对称。所以，求出x=2至n的所有与x互质的数的个数φ(x)的和（也就是线y=x右下角（因为φ(x)<x）所有能看见的点的个数）乘以2（对角线两旁的看见的点的个数）+3(那几个特殊点)即为所求。

求φ值时，利用下列性质：

if n能整除以p，也能整除以p^2，则φ(n)=φ(n/p)*p
if n能整除以p，但不能整除以p^2，则φ(n)=φ(n/p)*(p-1)。

这样，在线性求2至n的质数个数时将i当作n/p，prime[j]作为p，i*prime[j]作为n，（这样i%prime[j]就相当于n/p/p能否整除）同时更新以后的φ值即可。

#include <cstdio>

#include <cstring>

using namespace std;

const int MAX_N = 1010;

int v[MAX_N], prime[MAX_N], phi[MAX_N];

void Euler(int n)

{

	int primeCnt = 0;

	memset(v, 0, sizeof(v));

	for (int i = 2; i <= n; i++)

	{

		if (!v[i])

		{

			prime[primeCnt++] = i;

			v[i] = i;

			phi[i] = i - 1;

		}

		for (int j = 0; j < primeCnt && prime[j] <= n / i && prime[j] <= v[i]; j++)

		{

			v[i * prime[j]] = v[i];

			phi[i * prime[j]] = phi[i] * (i%prime[j] ? prime[j] - 1 : prime[j]);

		}

	}

}

int main()

{

	int n, testCase;

	scanf("%d", &testCase);

	for (int i = 1; i <= testCase; i++)

	{

		scanf("%d", &n);

		Euler(n);

		int ans = 0;

		for (int j = 2; j <= n; j++)

			ans += phi[j];

		printf("%d %d %d\n", i, n, ans * 2 + 3);

	}

	return 0;

}

　欧拉筛2：

void Euler(int *phi, int n)

{

	static int prime[MAX_N];

	static bool NotPrime[MAX_N];

	int primeCnt=0;

	memset(NotPrime,false,sizeof(NotPrime));

	phi[1] = 1;

	for(int i = 2; i <= n; i++)

	{

		if(!NotPrime[i])

		{

			prime[primeCnt++]=i;

			phi[i] = i - 1;

		}

		for(int j=0; j < primeCnt; j++)

		{

			if(prime[j] * i > n)

				break;

			NotPrime[prime[j] * i] = true;

			if(i % prime[j] == 0)

			{

				phi[prime[j] * i] = prime[j] * phi[i];

				break;

			}

			else

				phi[prime[j] * i] = (prime[j] - 1) * phi[i];

		}

	}

}

巴特西

POJ3090 Visible Lattice Points 欧拉筛

最新文章

热门文章