可以看出 (i, j) 能被看到，(i * k, j * k) 都会被挡住

暴力

所以 gcd(i, j) == 1 的话 ans ++

那么可以枚举一半(中轴对称)，求解答案，只能拿30分

#include <cstdio>

#include <iostream>

int n, ans;

inline int read()

{

	int x = 0, f = 1;

	char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

	return x * f;

}

inline int gcd(int x, int y)

{

	return !y ? x : gcd(y, x % y);

}

int main()

{

	int i, j;

	n = read();

	if(n == 1)

	{

		puts("0");

		return 0;

	}

	for(i = 1; i < n; i++)

		for(j = i + 1; j < n; j++)

			if(gcd(i, j) == 1)

					ans++;

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

	return 0;

}

　正解

可以看出，gcd(i,j) == 1 才能对答案有贡献，也就是互质，想到什么？phi 值

其实上面的暴力过程仔细来看也就是 phi 值的求解

#include <cstdio>

#include <iostream>

int n, ans;

int phi[500001];

inline int read()

{

	int x = 0, f = 1;

	char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

	return x * f;

}

inline void euler_phi()

{

	int i, j;

	phi[1] = 1;

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

		if(!phi[i])

			for(j = i; j < n; j += i)

			{

				if(!phi[j]) phi[j] = j;

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

			}

}

int main()

{

	int i, j;

	n = read();

	if(n == 1)

	{

		puts("0");

		return 0;

	}

	euler_phi();

	for(i = 1; i < n; i++) ans += phi[i];

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

	return 0;

}

巴特西

[luoguP2158] [SDOI2008]仪仗队（数论）

暴力

正解

最新文章

热门文章