关于“快速幂取模”有关问题，求指教

关于“快速幂取模”问题，求指教。
小弟初学C，遇到次方求模问题，这是我的代码~
#include<stdio.h>
int main()
{
    int N,i;
    long long a,b,c,num,m;
    scanf("%d",&N);
    while(N--)
    {
        scanf("%lld %lld %lld",&a,&b,&c);
        for(i=1,m=1;i<=b;i++)
            m=m*a;
        num=m%c;
        printf("%lld\n",num);
    }
    return 0;
}
但是在网上看有更好的方法可以快速幂取模，可是研究半天没研究懂= =，各位前辈能否指教下，详细的说说。。。下面是我在网上找到的快速幂取模的代码.
long exp_mod(long a,long b,long c)
{
    long t;
    if(b==0) return 1%c;
    if(b==1) return a%c;
    t=exp_mod(a,b/2,c);
    t=t*t/c;
    if((b&1)==1)
        t=t*a/c;
    return t;
}

------解决方案--------------------
代码中有些错误：

long exp_mod(long a,long b,long c)

{

    long t;

    if(b==0) return 1%c;

    if(b==1) return a%c;

    t=exp_mod(a,b/2,c);

    t=t*t%c;

    if((b&1)==1)

        t=t*a%c;

    return t;

}

二分法求幂：

t^n = t^(n/2) *t^(n-n/2);

由于：
(A * B) % M = ( (A % M) * (B % M) )%M
所以求a的模M幂也可以这样求：

(t^n)%M = ((t^(n/2)%M) * (t^(n-n/2)%M))%M

由于n/2与n-n/2相比可能相等（n为偶数）也可能多1（n为奇数）
进一步优化结果就是：
x = t ^ (n/2) %M
y = x * x % M;
如果n为奇数：y = y * t % M
return y

关于“快速幂取模”有关问题，求指教

相关推荐