计算x ^ 2和x ^(1/2)的效率更高的算法是什么?两者之间最好的是什么更有效?我要解决的问题是找到第n个“绿色”数字,如果N ^ 2以n结尾,则N是“绿色”数字。例如5 ^ 2 = 25、376 ^ 2 = 141376。这是我尝试的一些代码,但是要花很多时间来计算第十个数字:
我所做的基本上基本上是取x个数字中的i个获得i的最后x个数字,而没有加总功效,如果将总和1与累加器变量重合,则将这个最后x个数字与i进行比较。我正在考虑以另一种方式来解决这个问题,而不是为每个数字计算i ^ 2,而是计算数字的i ^(1/2)并进行相同的比较,可能会改善程序,因为只需要接受即可。计算以0,1,4,9,6,5结尾的数字。但是我知道真正的进步来自用另一种方式思考问题,而我丝毫没有丝毫想法。
def special_multiply(sa):
reverse_num = reversed(sa)
accumulator = 0
for i, digit in enumerate(reverse_num):
temp_chunk = sa[i:]
temp_pow = "".join(['1', '0' * i])
accumulator += int(digit) * int(temp_chunk) * int(temp_pow)
return accumulator % int("".join(['1', '0' * (i + 1)]))
def green(n):
count = 0
i = 0
while count <= n:
i += 1
si = str(i)
if si == str(special_multiply(si)):
count += 1
return i
换句话说,如果一个k
数字x
满足,则该数字为绿色
2 k
x = x mod 10 .
在中国剩余定理意味着,这个方程就相当于两个方程
2 k
x = x mod 2
2 k
x = x mod 5 .
求解这些方程等效于找到x^2 - x = x (x - 1)
以2
或的幂为模的多项式的根5
。Mod2
和mod5
有两种解决方案,分别是x = 0
和x = 1
。由于多项式的导数对于两个解2x - 1
都是非零mod2
和mod 5
,因此Hensel引理暗示0
并且1
实际上是唯一的对幂进行幂解的解决方案。
因此,有四个解决方案mod 10^k
,它们具有残基0
或1
mod2^k
和5^k
。例如376 mod 5^3 = 1
和376 mod 2^3 = 0
。对于每个k
,我们可以使用中国余数定理找到四个解(其中一个为零,因此不合格)。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句