2020.07.27 2020牛客暑期多校训练营（第六场）

无

无

Fraction Construction Problem

https://ac.nowcoder.com/acm/contest/5668/F

分类：数学

这题考察的数学知识很棒，证明也很精彩，所以作为推荐题目。

题目大意：给定两个整数 $a,b$，找出四个整数 $c,d,e,f$ 满足：

（1）$\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$

（2）$d<b$ 且 $f<b$

（3）$1\le c,e \le 4 \times 10^{12}$ （这个条件应该只是为了防 spj 读入溢出而已）

思路：这题需要分三种情况讨论：

（1）$a,b$ 间 gcd 不为 1：

此时只需要令 g = gcd(a, b)，则构造

$\frac{\frac{a}{g}+1}{\frac{b}{g}}-\frac{\frac{a}{g}}{\frac{b}{g}}=\frac{a}{b}$

即可。

（2）条件（1）不满足的时候 $b$ 的质因数数量不多于1个，此时题目无解。

原因是左边通分得到：

$\frac{cf-de}{df}$

考虑到 $\frac{a}{b}$ 没办法约分，所以 $a$ 中肯定不包含 $b$ 的质因数。设 $b=g^{k_b}$，则必有 $d=c_1g^{k_d}, f=c_2g^{k_f}$。由于通分的结果分母中肯定要约去 $g$ 的幂，则约分结果中分母的 $g$ 的次数一定小于 $min(k_d, k_f)$ 。由题目 $d, f < b$ 可知，$max(k_d, k_f) < k_b$。因此分母无论如何都凑不出 $g$ 的 $k_b$ 次幂，所以题目无解。

（3）条件（1）不满足的时候 $b$ 的质因数数量大于1个。

取 $d$ 为 $b$ 的其中一个质因数的最高次幂，令 $f=b/d$，易知 $d,f$ 间互质。左边通分后利用拓展欧几里得算法解出 $x,y$ 使得

$xf+dy = gcd(d,f) = 1$

令 $c=ax, e=-ay$ 即可。

无

无

无