簡単約分
https://gyazo.com/11d10ff87e903baa96b7c276ede6e35c
どうやって思いつくのかという話があったので解説を書く
aの桁数をNとする
$ \frac{10a+b}{10^Nc+a} =\frac{b}{c} なので分母を払って $ (10a+b)c=(10^Nc+a)b である
aについて整理すると $ bc(10^N-1)+a(b-10c) = 0
以降簡単のために$ d+ae = 0と書く
任意の数で余りをとっても等式が成立するので十分大きな素数Pで割る
$ d+ae\equiv 0 \pmod{P}
この時、aは $ a \equiv -de^{-1} \pmod{P}
よって$ b,c,N を決めれば$ a が決まる
正しく求まってるか確認する(Nが求めたaの長さに一致しないことがほとんど)
Pを複数個用意すると中国剰余定理を使って大きなaを求めることもできる Tweetまとめ
nishio: どうやって思いつくのかという話があったけど(10a+b)/(c×10^len(a)+a)=b/cなので(10a+b)c=(c×10^len(a)+a)bで、全部整数なので任意の数で余りをとっても等式が成立するので以下略(スマホで数式描くのつらすぎ nishio: b,cが互いに素である場合、こんな感じでaはbcの倍数であることがわかる、後は最後の式だがaとbcが素でないので逆元がどうなるかというと… https://gyazo.com/cca80e7ace0ea2b3aeaff657165a6978
nishio: 僕が続きを計算してる間に元のでかい分数で上記の等式が成立するのを確かめててください 712158808933002481389578163771 mod 7 * 41
https://gyazo.com/d8c779d5ec929797f9cb17a8bb7969bd
nishio: あれー、なんか他に条件がいるかな、これだけだと正解以外にたくさん解がでてしまう -----
nishio: 12_307692 / 307692_3 = 4 41_302211 / 302211_3 = 41 / 3
57_301587 / 301587_3 = 19
71_301272984441 / 301272984441_3 = 71/3
nishio: そうか中国剰余定理(CRT)だ！と思いついて、式をaについて整理してから10^9程度の十分大きな素数二つで剰余をとってCRTしたけど、結局のところ10^9より小さい解もあったので本質はCRTではなく、十分大きな素数を持ってくればフェルマーの小定理で逆元が求まるところですね https://gyazo.com/98dd3480a3bf250b63cdfb1fc04fe99a
nishio: いまこういう自明なやつを取り除いて一覧を出す準備をしてます 5050505050505050_5 / 50_5050505050505050 = 1/10
nishio: bが1桁、cが最大2桁の範囲で10倍のやつを除いて297個ありますね。この列挙に0.2秒でした。 nishio: あ、書き忘れたけどaの桁数は2〜17にしました。出力を見ればわかるように桁数を制限しないと無数にあります。 関連