用数论的知识解决模幂运算

 

在数学上，如果数A与数B对M取模后得到的值相等，即A%M=B%M，则称A与B是关于模M同余，记为A≡B。

此外对于同余运算有如下定理：（自己推导的话也可以轻易得证）

（1）若A≡B，则存在常数D，使得A+D≡B+D ;

（2）若A≡B，则存在常数D，使得A*D≡B*D  ;

（3）若A≡B，则存在常数n，使得A^n≡B^n  ;

基于此原理，对于模幂运算，即A^n%m的运算可以，通过A^n≡B^n（前提A≡B）的形式来化简，辅以定理（1）和（2），可以实现以较短的时间进行求解。

程序如下：

/*===========================================
 *
 * 函 数 名：ModCal
 *
 * 参
数：
 *
int digit：底数
 *
int n
：指数
 *
int m
：模数
 *
 * 功能描述：运算数论原理解决模幂运算
 *
 * 返 回 值：返回模幂运算的结果
 *
 * 抛出异常：
 *
 * 作者：crazyhf 2012/05/04
 *
 ============================================*/

int ModCal( int digit, int n, int m )
{

int muldigit, i ;

digit %= m ;


if ( !n || digit == 1 ) return 1 ;


for( i = 1, muldigit = digit;

i < n && muldigit < m;

muldigit *= digit, i++ ) ;


if( i == n ) return muldigit %= m ;


return ModCal( muldigit, n / i, m ) * ModCal( digit, n % i, m ) % m ;
}

模幂运算功能的测试代码如下：

# include <iostream>
using std::cin ;
using std::cout ;
using std::endl ;
int main( int argc, char **argv )
{
while( 1 )
{
int digit, n, m ;
if( cin >> digit >> n >> m )
{
cout << ModCal( digit, n, m ) << endl ;
}
}
return 0 ;
}