题目：一个数最后一位是6，移动到首位是原来数的三倍，求这个数
要求：速度最优
大神们快来踊跃探讨~~~
记所求数为x，为一个m+1位数，记为
$$ x = \overline {a6} $$
，其中a为一个m位数。则有：
$$ 3x = \overline {6a} $$
即
$$ 3 \times (10a+6) = 6 \times 10^m + a $$
化简得：
$$ 29a = 6(10^m-3) $$
即：
$${29 \over 6} = {{10^m-3} \over {a}} $$
因为：$$(29, 6) = 1$$，所以必须有：
$$ 10^m \equiv 3 (mod 29) $$
该方程最小解为
$$ m = 27 $$
由费马小定理，所有解为：
$$ m = 28k - 1 $$
代回原式得所有解：
$$ x = (10^{28k-1}-3) \times {6 \over 29} \times 10 + 6 $$
公式app无法显示，请在web端查看
Update: 费马小定理那里有些跳步，详细如下：
因为 29 是质数，且
$$ (29, 10) = 1$$
由费马小定理有
$$ 10^{28} \equiv 1 ( mod 29) $$
并且 28 为 10 模 29 的阶
从而形如
$$ 27 + 28k $$
也就是
$$ 28k - 1 $$
的数也是该方程的解，并且为所有解。
下午看到這題的時候就有了個想法, 手邊沒電腦只好等到現在...
後來看到 @citaret 的答案就發現剛好是反向的想法, 下面是我的作法:
x = 6
last_carry = 0
result = 6
radix = 10
while True:
c1, x = divmod(x * 3, 10)
c2, x = divmod(x + last_carry, 10)
last_carry = c1 + c2
if x==6 and last_carry==0:
return result
result += (x * radix)
radix *= 10想法就剛好是反過來, 我一步一步地乘上去
-
每次把
x乘 3把個位數加上
last_carry就是下次的x把十位數的進位留下來當作下次的
last_carry做到
x==6且無進位的時候
用圖來思考長這樣:
0 <-- last carry
\
1 8 = 6 X 3
\ (0 + 8 = 8)
2 4 = 8 X 3
\ (1 + 4 = 5)
1 5 = 5 X 3
...用 timeit 稍微測了一下時間(各運行 1000000 次), 共測三次:
# first
dokelung: 17.301649590954185
citaret: 18.24915363173932
# second
dokelung: 19.257807812653482
citaret: 17.994877750985324
# third
dokelung: 17.0617663115263
citaret: 18.355605391785502時間看起來差不多, 不過我自認為代碼沒有很漂亮...
我回答過的問題: Python-QA
先贴上一版：
x = 6
xs = []
while True:
xs.append(x // 3)
x = x % 3 * 10 + x // 3
if x == 6:
print ''.join(str(x) for x in xs)
break输出：
2068965517241379310344827586
原理是手算，把每次得到的商的末位补到被除数的最后，然后继续除法，直到末位为6，且余数为0停止。