如果只要得到 t = t % n * 10 + 1 这个式子,我觉得可以看出来,连竖式都不要,用同余的表达式让人好理解。或者换个角度想,如果不是10进制,是13进制又或者是12889,。。。再用竖式推出类似的式子看看,但是用我的方法一样可以看出来。
根据我上面用欧拉定理的推导,其实可以发现,不管是多少进制,10,12889.。。,只要和n互质,φ(m)总是能满足条件的,但很容易发现它不是最小的那个数。还有1个定理
若t为a对模n的阶,s为某一正整数,满足a**s = 1 (mod n),则s必为t的倍数
所以要求的那个最小正式肯定是φ(m)的倍数。比如
n=11时,
φ(m) = φ(11) = 11 - 1 = 10 = 2 * 5,最小的整数只能是2,5,10,很容易发现2满足条件。
n=3时,
φ(m) = φ(9*3) = 3**3 = (3-1) * 3**2 = 18,最小的整数只能为2,3,6,9,12,18,很容易发现3满足条件。
n=21时,
φ(m) = φ(3*7) = (3-1)*(7-1) = 2*3*3,最小的整数只能为2,3,6,9,12,18,很容易发现6满足条件。
n=231时,
φ(m) = φ(9*3*7*11) = (3-1)*3**2 * (7-1) * (11-1) = 6 * 10 * 2 * 9 = 2 * 5 * 3**3 * 2**2,很显然 2**2可以去掉,所以这个数为2*5*3**3,
最小整数只能为(3,9,27,5,15,45,145),2*(3,9,27,5,15,45,145),至于是哪个数我没去算过。
这里面的推导,应该还可以去掉一些不必要的情况。所以这题可以转换为因式分解。
代码不想写,一写代码就发愁。我只是觉得这是一个思路,并不是说性能比用最简单的for循环要好,如果要我写代码,估计也会写出你提供的那个。通常境况下,或者是超大数,这个方法的性能也是很好的。