caioj 1161 欧拉函数3：可见点数

（x, y）被看到仅当x与y互质

由此联想到欧拉函数

x=y是1个点，然后把正方形分成两半，一边是φ（n）

所以答案是2*∑φ（n）+1

#include<cstdio>

#include<cctype>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 1123;

ll euler[MAXN];

void get_euler()

{

	_for(i, 1, MAXN) euler[i] = i;

	_for(i, 2, MAXN)

	{

		if(euler[i] == i)

			for(int j = i; j <= MAXN; j += i)

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

		euler[i] += euler[i-1];

	}

}

void read(ll& x)

{

	int f = 1; x = 0; char ch = getchar();

	while(!isdigit(ch)) { if(ch == '-1') f = -1; ch = getchar(); }

	while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }

	x *= f;

}

int main()

{

	get_euler();

	ll n; read(n);

	_for(i, 1, n)

	{

		ll x; read(x);

		printf("%d %lld %lld\n", i, x, 2 * euler[x] + 1);

	}

	return 0;

}

巴特西

caioj 1161 欧拉函数3：可见点数

最新文章

热门文章