UVA10820 交表 Send a Table

\(\Large\textbf{Description:} \large{输入n，求有多少个二元组(x,y)满足：1\leqslant x,y\leqslant n，且x和y互素。}\)

\(\Large\textbf{Solution:} \large{不难发现除了(1,1)外，其他二元组的x，y都不相等。设满足x < y的二元组有g(n)个，那么答案为2\times g(n) + 1。}\)

\(\large{其中g(n)=\sum_{i=2}^n\Phi(i)}。\)

\(\Large\textbf{Code:}\)

#include <cmath>

#include <cstdio>

#include <algorithm>

#define LL long long

#define gc() getchar()

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

using namespace std;

const int N = 5e4 + 5;

int n, cnt, prime[N], phi[N];

LL sum[N];

bool vis[N];

inline int read() {

	char ch = gc();

	int ans = 0;

	while (ch > '9' || ch < '0') ch = gc();

	while (ch >= '0' && ch <= '9') ans = (ans << 1) + (ans << 3) + ch - '0', ch = gc();

	return ans;

}

inline void euler() {

	phi[1] = 1;

	rep(i, 2, N) {

		if (!vis[i]) prime[++cnt] = i, phi[i] = i - 1;

		for (int j = 1; j <= cnt && i * prime[j] <= N; ++j) {

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

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

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

				break;

			}

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

		}

	}

}

int main() {

	euler();

	rep(i, 1, N) sum[i] = sum[i - 1] + phi[i];

	n = read();

	while (n) {

		printf("%lld\n", 2 * sum[n] - 1);

		n = read();

	}

	return 0;

}

\(\large\color{pink}{by\quad Miraclys}\)

巴特西

UVA10820 交表 Send a Table

最新文章

热门文章