需要设计一个数字运算算法

Question

我偶然发现了这个问题:

7电源7是823543.哪个7的高功率以823543结束？

我该怎么办呢？我提出的那个非常慢,它继续乘以7并检查结果的最后6位数.

我试过Lou的代码:

int x=1;
    for (int i=3;i<=100000000;i=i+4){
            x=(x*7)%1000000;
            System.out.println("i="+ i+" x= "+x);
            if (x==823543){
                System.out.println("Ans "+i);}
            }

CPU听起来像一个压力锅,但无法得到答案:(

Answer 1

乘以模10 ^ 6.看到这个Lua代码.

local x=1
for i=1,100000 do
        x=(x*7) % 1e6
        if x==823543 then print(i) end
end

Answer 2

你可以使用欧拉对费马小定理的推广,它适用于你的情况说,对于任何不能被2或5整除的数字a,a到400000的幂等于1模10 ^ 6.这意味着7 ^ 400000等于1,而7 ^ 400007等于823543模10 ^ 6

可能有较小的7的幂也等于一个模10 ^ 6.任何这样的权力应该是400000的除数.所以如果你搜索400000的所有除数,你应该找到你的答案.