一个奇奇怪怪的问题

学术版

览遍千秋 @ 2021-07-29 21:39:59

众所周知，\dfrac{68}{56} 上下同时划掉一个 6，得到 \dfrac{68}{56} = \dfrac{8}{5}，这样的化简方法显然是错误的。

但在某些情况下，如 \dfrac{16}{64}=\dfrac{1}{4}却是正确的。

将这样的化简规则，明确为上下同时划去尽可能多的相同数字。

求问这样的分数是否存在一定的性质，或者说，能以优于 O(n^2) 的时间复杂度求出分子分母在 [1,n] 范围内的所有符合上述性质的分数。

by damage @ 2021-07-29 23:40:58

（挺有意思的我就试试n=2的情况）

若消去的数字在分子和分母上对应同样的位数，如同为个位或十位，显然只有$\overline{a0} (1\leq{a}\leq{9})$形式的数字满足。分子和分母为满足上述条件的$9$个数字中的任意一个即可，但不可相同，故有$72$种情况。 若形如$\frac{\overline{ax}}{\overline{xb}}(a\neq b)$（另一种形式同理，即分子分母对调），则化简后有$x=\frac{9ab}{10a-b}$，枚举$a$并判断是否存在$b$能否整除即可（然而我还是不会，但至少可以更优） ### （然而上面全是废话，当我什么也没说） 我连暴力枚举都不会，只会$O(n^2log_{10}n)$的 其实也不一定唯一吧，比如$\frac{114514}{1919}$，删去尽量多的话还是有$3$种不同化简方法的 ```%%%expect2004```
|