?? 模取冪運算(計算a^b mod n).cpp
字號:
#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));
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -