一上来看见 \(crimson000\) 的闲话给我看舍了。
一直不会\(D\)人现在会了???,以后直接套这个模板就行了吧?
因为来的时间太短没来得及写完一道题。
看见 \(LiJoQiao\) 的闲话,学了下埃及分数,然后贺了个贪心解法,好像是正确的?
给定一个分数 \(f\),求拆成埃及分数的最优形式
第一步找到最小的 \(n\),使要找的数 \(f>\frac 1n\),输出 \(\frac{1}{n}\),计算 \(f=f-\frac{1}{n}\),若此时的数是埃及分数,输出并结束,否则设 \(F=A/B\),\(D=B/A\) 的商,余数为 \(K\)
则有
\[B=A\times B+K \\ \frac BA=D+\frac KA<D+1
\\
\frac AB>\frac{1}{D+1}\]
记 \(C=D+1\),下一步就是进一步计算
\[\frac AB-\frac 1C=\frac {A\times C-B}{B\times C}
\]
下一步把分子化为\(A\times C-B\),分母化为 \(B\times C\) 的问题。
证明来自CSDN(
求教教???