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$ 即可。
无
无
无