自动搬运

查看原文

来自洛谷，原作者为

	djc AFO|渺渺兮予怀，望美人兮天一方

搬运于2025-08-24 22:51:55，当前版本为作者最后更新于2023-10-29 08:36:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定一个正整数 $n$，构造出若干个形如 $\frac{a_i} {b_i}$ 的真分数，使得 $\sum_{i=1} ^{k} \frac{a_i} {b_i} =1-\frac {1} {n}$，且 $b_i$ 是 $n$ 的因数。

题目分析

由于 $b_i$ 是 $n$ 的因数，所以我们直觉上先把 $n$ 分解一下:

• $n = p^m$

  在这种情况下，无解。如果 $n = p^m$，那么 $b_i = p^{k_i}(k_i\le m)$，并且每个 $b_i$ 都差了 $p^x$ 倍。设最大的一个 $b_i$ 为 $t$，则通分后的分母为 $t$，而 $t \le n$，所以不可能凑成 $\frac{n-1}{n}$。

• $n$ 的质因数大于等于 $2$ 种

  首先，在这种情况下，如果存在答案，那么 $k$ 一定可以等于 $2$。因为 $b_i | n$，且 $lcm(b_1,b_2,\dots,b_k) = n$，任意选取两个，$lcm(b_x, b_y)|n$，如果 $k>2$，我们可以把它们凑成两个。

  $$\frac{a}{x} + \frac{b}{y} = \frac{n-1}{n}$$

  所以算法的第一步就出来了，$x$ 和 $y$ 任选，只要是 $n$ 的因数且最小公倍数等于 $n$ 就可以了，然后我们再看 $a$ 和 $b$，是否对于任意的 $x$ 和 $y$ 都存在正整数解 $(a,b)$ 且 $a < x,b<y$ 呢？

  先做一个转换，同乘 $xy$：

  $$ay+bx=\gcd(x,y)\cdot(n-1)$$

  观察这个式子，在学习拓展欧几里得算法时我们学过，$ax+by$ 一定是 $\gcd(a,b)$ 的倍数，否则无解，由于 $\gcd(x,y)\cdot(n-1)$ 一定是 $\gcd(x,y)$ 的倍数，所以一定是有解的。

  还有就是要证明存在一个 $a<x,b<y$ 的情况下的解，设 $a$ 已知，$1\le a < x$，则 $b = \frac{\gcd(x,y)\cdot(n-1)-ay}{x}$。设 $x' = \frac{x}{\gcd(x,y)},y' = \frac{y}{\gcd(x,y)}$，则

  $$b = \frac{(n-1)-ay'}{x'}$$

  若有解，则需要 $b$ 是一个整数，也就是

  $$(n-1)-ay' \equiv 0 \pmod{x'}$$

  我们看 $ay'$，由于 $y'$ 与 $x'$ 互质，所以当 $a\in [0,x-1]$，$ay'\pmod{x'}$ 的值都不相同。

  证明：如果有两数相同，$a_1 y' = k_1x'+t,a_2y' = k_2x'+t$，则 $(a_1 - a_2)y' = (k_1 - k_2)x'$，$a_1-a_2$ 需要是 $x'$ 的倍数。

  又因为当 $a=0$ 时，$(n-1) \pmod{x'}$ 一定不为 $0$，所以在 $1$ 到 $x-1$ 中一定有一个 $a$ 使得 $(n-1)-ay' \equiv 0 \pmod{x'}$。

代码实现

经过以上分析，代码就可以写出来了。我们先把 $n$ 分解质因数，然后选取 $x$ 和 $y$，使 $\gcd(x,y)=1,x\cdot y = n$。然后从 $1$ 到 $x-1$ 枚举 $a$，每次进行一个判断即可。时间复杂度 $O(\sqrt{n})$。

最后贴上代码，码风很丑轻点喷。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100005
inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

int vis[maxn], prime[maxn], n, m;

void init() {
	for (int i = 2; i <= 100000; i++) {
		if (!vis[i]) prime[++m] = i, vis[i] = 1;
		for (int j = 1; j <= m && prime[j] * i <= 100000; j++) 
			vis[prime[j] * i] = 1;
	}
}

struct node {
	int v, cnt;
};

vector<node> a;

int ksm(int a, int b) {
	int res = 1;
	for (; b; b >>= 1) {
		if (b & 1) res = res * a;
		a = a * a;
	}
	return res;
}

signed main() {
	init();
	n = read();
	for (int i = 1; i <= m; i++) {
		if (n % prime[i] == 0) {
			int tmp = n, cnt = 0;
			while (tmp % prime[i] == 0) {
				cnt++;
				tmp /= prime[i];
			}
			node nw; nw.cnt = cnt, nw.v = prime[i];
			a.push_back(nw);
			break;
		}
	}
	if (a.empty() || ksm(a[0].v, a[0].cnt) == n) {
		puts("NO");
		return 0;
	}
	puts("YES");
	int x = ksm(a[0].v, a[0].cnt);
	int y = n / x, a, b;
	for (a = 1; a < x; a++) {
		if ((n - 1 - a * y) % x == 0) {
			b = (n - 1 - a * y) / x;
			break;
		}
	}
	cout << 2 << endl;
	cout << a << " " << x << endl << b << " " << y;
}