23 solutions

  • 3
    @ 2022-6-19 12:40:23

    此题解是 JuliaRoadmap 项目的一部分

    题解里很多人用递归的方法,这里不再阐述。注意到可以对bb 进行二进制拆分,例如对于12=(1100)212=(1100)_2,只需从左到右循环即可

    题目中限定 b<231b<2^{31},使用以下代码

    function main()
        a=parse(Int, readuntil(stdin,' '))
        b=parse(Int, readuntil(stdin,' '))
        p=parse(Int, readline())
        a%=p
        ans=1
        for i in 31:-1:0
            sign=(b>>i)&1 # 位运算技巧
            if sign==0
                ans=ans*ans%p
            else
                ans=(ans*ans%p)*a%p
            end
        end
        print(ans)
    end
    main()
    

    评测结果492~614ms

    Information

    ID
    171
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    2
    Tags
    # Submissions
    808
    Accepted
    278
    Uploaded By