此题如何求解

liexi

1、已知2的N次方为A，且A的最后三位数为112，求N是多少，在些向各位请教下此题的思路。
2、已知2的N次方为A，且A的前面三位数为112，求N是多少，在些向各位请教下此题的思路。

lincong999

因为 2^6=64<112  2^7=128〉112  2^10=1024<1112  2^11=2048〉2112
所以 N>11
设K1= 3 4 5.。。。
2^N=A=1000*K1+112
2^(N-1)=50*K1+56
2^(N-2)=25*K1+28
2^(N-3)=12.5*K1+14

设K1=2*K2+1 （K2=1 2 3 4 5.。。。）
2^(N-3)=12.5*（2*K2+1）+14=25*K2+40.5
此等式不成立 因此K1为偶数

设K1=2*K2 （K2=1 2 3 4 5.。。。）
2^(N-3)=12.5*（2*K2）+14=25*K2+14
2^(N-4)=12.5*（2*K2）+14=12.5*K2+7

。。。。。。。
估计不会快速收敛
一开始的等式可能需要改成
2^N=A=1000*K1-888
这样也许好算些

count

1.
问题转化为 f(N) == 112
其中函数 f(N) = 2^N mod 1000 的周期不会超过 1000/2=500
所以穷举就行了
结果是 N = 89
2^89 = 618970019642690137449562112
更进一步, f(N) 的周期可以通过欧拉定理(费马小定理的推广)得到, 是 400
所以 N=400k+89 就是所有 N 了

2.
转化为 2^N == (1.12+r) * 10^m
两边求10为底的对数
N*lg2 == lg(1.12+r) + m
其中, r属于[0, 0.01), m 是整数
然后就是穷举 N 或者 m 使另一个是整数, 穷举 m 应该有利些.
比如检验 abs(N*b mod 1 - amid) < epsilon
        amid    = (lg(1.13) + lg(1.12))/2
        epsilon = (lg(1.13) - lg(1.12))/2
当然啦, 其中的 lg 要用高精度.

不知有没更好的办法(连分数?)

结果是
2^ 50 = 1.12589990684262e15
2^ 535 = 1.12472844863580e161
2^ 731 = 1.12960558348329e220
2^ 1020 = 1.12355820928895e307
2^ 1216 = 1.12843026965370e366
2^ 1505 = 1.12238918753389e453
2^ 1701 = 1.12725617869572e512
2^ 1990 = 1.12122138210376e599
2^ 2186 = 1.12608330933699e658
2^ 2475 = 1.12005479173303e745
2^ 2671 = 1.12491166030649e804
2^ 2867 = 1.12978958961065e863
2^ 3156 = 1.12374123033451e950
2^ 3352 = 1.12861408432933e1009
2^ 3641 = 1.12257201815266e1096
2^ 3837 = 1.12743980211882e1155
2^ 4126 = 1.12140402249388e1242
2^ 4322 = 1.12626674170655e1301
2^ 4611 = 1.12023724209241e1388
2^ 4807 = 1.12509490182129e1447
2^ 5003 = 1.12997362571154e1506
2^ 5292 = 1.12392428119313e1593
2^ 5488 = 1.12879792894730e1652
2^ 5777 = 1.12275487855347e1739
2^ 5973 = 1.12762345545310e1798
2^ 6262 = 1.12158669263504e1885
2^ 6458 = 1.12645020395616e1944
2^ 6747 = 1.12041972217189e2031
2^ 6943 = 1.12527817318506e2090
2^ 7428 = 1.12410736186966e2236
2^ 7624 = 1.12898180351248e2295
2^ 7913 = 1.12293776874117e2382
2^ 8109 = 1.12780713870343e2441
2^ 8398 = 1.12176939253210e2528
2^ 8594 = 1.12663369609070e2587
2^ 8883 = 1.12060223197630e2674
2^ 9079 = 1.12546147440266e2733
2^ 9564 = 1.12429047236896e2879
2^ 9760 = 1.12916570802974e2938

N 有 +196 +289 (或其组合)的循环. 大致是因为 2^196, 2^289 的开头几位接近 100.. 并且一个偏大, 一个偏小.