洛谷 1226_取余运算||快速幂_快速幂

发布于 2019-05-08  9 次阅读


题目描述

输入b,p,k的值,求b^p mod k的值。其中b,p,k*k为长整型数。


思路

就是一个快速幂。
没了
1.洛谷用lld
2.要用long long
O(log₂N)


#include 
int main()
{
    long long n,m,x;
    scanf("%lld%lld%lld",&n,&m,&x);
    long long xx=n,yy=m;
    long long t=1;
    while (m>0)
    {
        if (m & 1)
            t=(t*n)%x;
        n=(n*n)%x;
        m>>=1;
    }
    printf("%lld^%lld mod %lld=%lld\n",xx,yy,x,t);
}
]]>