2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_3
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_3 [2020/07/24 10:59] hardict |
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_3 [2020/07/24 11:12] (当前版本) hardict [F. Fraction Construction Problem] |
||
|---|---|---|---|
| 行 101: | 行 101: | ||
| by Hardict | by Hardict | ||
| + | ===== F. Fraction Construction Problem ===== | ||
| + | |||
| + | 首先$d=f$即$gcd(a,b)>1$解是显然的 | ||
| + | |||
| + | $(d,f)=x,\frac{c}{d}-\frac{e}{f}=\frac{c\frac{f}{x}-e\frac{d}{x}}{\frac{df}{x}}$ | ||
| + | |||
| + | 不妨$(d,f)=1$.转换为$\frac{cf-ed}{xdf};xd,xf \leq b$ | ||
| + | |||
| + | 我们即可知道$b$的两个不同素因子p,q，然后$d=p,f=q$ | ||
| + | |||
| + | 利用$exgcd$求得$cf-ed=1$,$c$取最小正数解$c_{0}$ | ||
| + | |||
| + | 故整体解为$c=ac_{0},e=ae_{0},d=px,f=qx,x=\frac{b}{pq}$ | ||
| + | |||
| + | 而若$b$为$1$或素因子的幂是无解的 | ||
| + | |||
| + | by Hardict | ||
| ===== G. Operating on a Graph ===== | ===== G. Operating on a Graph ===== | ||
2020-2021/teams/alchemist/2020_nowcoder_multiuniversity_3.1595559574.txt.gz · 最后更改: 2020/07/24 10:59 由 hardict
