大数取模法

求 a^b mod n

 

a^b 直接求会非常大，甚至超出64位能表示的范围；

 

 

int modular_exponent(int a,int b,int n)
{
    int ret = 1;
    for ( ; b; b>>=1,a=a*a%n )
    {
        if ( b&1 )
            ret = ret*a %n;
    }
        return ret;
}


*************************************************************

回去搞本数论研究下去。

*************************************************************