【CodeForces-1089F】Fractions

题意#

给定正整数 $n\leq 10^9$，需要构造出不超过 $10^5$ 个真分数，满足：

• $\frac{a_1}{b_1}+\frac{a_2}{b_2}+\cdots+\frac{a_t}{b_t}+\frac{1}{n}=1$.
• 对每个分数，$b_i<n$ 且 $b_i\mid n$.

若无解，输出 $-1$，否则给出一组可行解。

分析#

先将 $n$ 质因数分解，分下列情况讨论。

一#

首先考虑特殊情况。$n = p^m$，其中 $p$ 是质数。

要选一个因数作为分母，发现 $n$ 的任意一个因数 $b$，都一定是 $p^a$ 的形式。

因为分母为 $1$ 时不合题意，所以在 $1$ 之外，我们任选 $n$ 的两个因子，不妨设为 $c, d$，一定有 $\gcd(c, d)\neq 1$.

又因为 $\gcd(n-1, n)=1$，而 $\gcd(c, d)\neq 1$。以 $c, d$ 作为分母，一定不合法。

也就是说，当 $n=p^m$ 时，不存在合法解。

二#

对于其他情况，$n$ 一定可以被表示为两个互质的数的乘积。一种构造方法是：

将 $n$ 质因数分解，不妨 $n=p_1^{m_1}p_2^{m2}\cdots p_t^{m_t}$，令 $x=p_1^{m_1}$，$y=p_2^{m_2}\cdots p_t^{m_t}$，显然 $xy=n$ 且 $\gcd(x, y)=1$.

为了方便，我们钦定 $x\leq y$。如果按照上面的方法得到的 $x>y$，交换 $x, y$ 即可。

当 $k=2$ 时，设题目所求的 $\frac{a_1}{b_1}=\frac{c}{x}$，$\frac{a_2}{b_2}=\frac{d}{y}$.

我们需要求出一组 $(c, d)$ 满足 $\frac{c}{x}+\frac{d}{y}=1-\frac{1}{n}\Rightarrow \frac{c\cdot y+d\cdot x}{xy}=\frac{n-1}{n}$.

因为 $xy=n$，这等价于满足：

继续整理，把 $c\cdot y$ 移到右侧，得到：

注意 $c, d\in \Bbb{Z}^+$。

先不考虑 $d$ 的正负性。由于 $x\mid n$，有：

想要找到满足 $x\mid (1+c\cdot y)$ 的 $c$，考虑直接枚举。

注意到 $\gcd(x, y)=1$。当 $c$ 取 $1, 2, \cdots x-1$ 时，都有 $x\nmid (c\cdot y)$，所以 $c\cdot y$ 的取值构成 $\operatorname{mod} x$ 的完全剩余系。

也就是说，当 $c$ 遍历 $1\sim x-1$ 时，$c\cdot y\bmod x$ 的取值两两不同，也恰好完全覆盖了 $1\sim x-1$.

因此，一定存在 $c\in[1, x-1]$ 满足 $x\mid (c\cdot y+1)$.

再看 $d$ 的正负性。由于 $1+c \cdot y \leq 1+(x-1) \cdot y=1+xy-y=n-(y-1) < n$，所以 $n-(1\cdot y)>0$.

因此，一定有 $d=\frac{n-1-cy}{x}>0$.

综上#

我们先按照 $x=p_1^{m_1}$，$y=p_2^{m_2}\cdots p_t^{m_t}$ 的方法找到 $(x, y)$.

之后，在范围 $1\sim x-1$ 中枚举 $c$，找到满足 $x\mid(c\cdot y+1)$ 的 $c$，计算出 $d=\frac{n-1-cy}{x}$。

$(\frac{c}{x}, \frac{d}{y})$ 即为满足题意的两个分数。

时间复杂度#

找到 $(x, y)$ 的部分，需要对 $x$ 分解质因数，时间复杂度为 $\mathcal{O}(\sqrt{n})$.

枚举 $c$ 的部分，因为我们钦定了 $x\leq y$，把 $[1, x-1]$ 看作 $x$ 个数，那么：

所以总时间复杂度是 $\mathcal{O}(\sqrt{n})$ 的。

代码#

int n;
vector<int> fac;
int main() {
	scanf("%d", &n);
	int p1 = -1;
	for(int i = 2; i * i <= n; i++) {
		if(n % i == 0) {p1 = i; break;}
	}
	if(p1 == -1) p1 = n;
	int x = p1, y = n / p1;
	while(y % p1 == 0) y /= p1, x *= p1;
	if(y == 1) {
		cout << "NO" << endl;
		return 0;
	}
	int ansc, ansd;
	for(int c = 1; c <= x - 1; c++) {
		if((c * y + 1) % x == 0) {
			ansc = c; ansd = (n - 1 - c * y) / x;
			break;
		}
	}
	cout << "YES\n2\n" << ansc << " " << x << "\n" << ansd << " " << y << endl;
	return 0;
}