2020-2021:teams:the_great_wave_off_kanagawa:week_summary_8

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:the_great_wave_off_kanagawa:week_summary_8 [2020/07/31 17:40]
airbust
+++ 2020-2021:teams:the_great_wave_off_kanagawa:week_summary_8 [2020/07/31 18:01] (当前版本)
lkw981105 [Ket98]
@@ 行 17: / 行 17: @@
 ==== Ket98 ====
-Clam and Fish
+Fraction Construction Problem
-分类：思维
+https://ac.nowcoder.com/acm/contest/5668/F
-题目大意：有$n$个笼子，里面可能有（1）空（2）蛤蜊*1（3）鱼*1（4）鱼*1和蛤蜊*1。有四种操作：（1）把蛤蜊做成饲料供后边的笼子来使用（2）用饲料捕捉鱼（3）如果笼子有鱼，可直接捕捉鱼（4）什么都不做。问最多可以捕捉多少鱼？
+分类：数学
-思路：题目可能比较长，但其实矛盾点就是在蛤蜊*1的笼子应该是拿去作饲料还是拿去捕捉鱼。这里有两种解法。
+这题考察的数学知识很棒，证明也很精彩，所以作为推荐题目。
-比赛的时候我使用倒序读取，need记录目前所需的饲料。碰到空笼子则need++，碰到有蛤蜊的笼子分两种情况（1）need==0时用于捕捉鱼（2）need!=0时用于做饲料。有鱼的笼子全部捉鱼即可。
+题目大意：给定两个整数 $a,b$，找出四个整数 $c,d,e,f$ 满足：
-第二种是顺序读取，贪心把所有的蛤蜊做成饲料，最后把剩下的饲料/2，一半用于做饲料，一半用于捉鱼。
+（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$ 即可。
 ===== 个人 =====

2020-2021/teams/the_great_wave_off_kanagawa/week_summary_8.1596188421.txt.gz · 最后更改: 2020/07/31 17:40 由 airbust