CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2020/07/26 -- 2020/07/31 周报 ======

===== 团队训练 =====

2020.07.27 [[https://ac.nowcoder.com/acm/contest/5671|2020牛客暑期多校训练营（第六场）]]

===== 本周推荐 =====

==== airbust ====

无

==== kazamori ====

无

==== Ket98 ====
   
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$ 即可。
===== 个人 =====


==== airbust ====

=== 比赛 ===

无

==== kazamori ====

=== 比赛 ===

无

==== Ket98 ====

=== 比赛 ===

无
CVBB ACM Team

用户工具

站点工具

页面工具
