模取幂运算（计算a^b mod n）.cpp

来自「acm中各种代码」· C++ 代码 · 共 55 行

 #include<stdio.h>
 /*********************************************   
    
   返回x的二进制长度   
    
   *********************************************/   
   int    BitLength(int    x)   
   {   
   int    d    =    0;   
   while    (x    >    0)    {   
   x    >>=    1;   
   d++;   
   }   
   return    d;   
   }   
    
   /*********************************************   
    
   返回x的二进制表示中从低到高的第i位   
   ，最低位为第一位   
    
   *********************************************/   
    
   int    BitAt(int    x,    int    i)   
   {   
   return    (    x    &    (1    <<    (i-1))    );   
   }   
    
   /*********************************************   
    
                   模取幂运算    计算a^b    mod    n   
    
   *********************************************/   

 int    Modular_Expoent(int    a,int    b,int    n)   
   {   
    
           int    i,    y=1;   
           for    (i    =    BitLength(b);    i    >    0;    i--)   
           {     
                     y    =    (y*y)%n;   
                     if    (BitAt(b,i)    >    0)     
     y    =    (y*a)%n;   
           }   
         return    y;   
    
   } 

int main()
{
    int a,b,n;
    while(scanf("%d %d %d",&a,&b,&n) != EOF)
    printf("%d\n",Modular_Expoent(a,b,n));    
}