求a的b次方对p取模

原创
2021/12/02 13:17
阅读数 253

题目:

求a的b次方对p取模   

a^b % p

 

思路:

b的二进制有n位 ,从低位到高位分别为c0, c1,..., c(n-1),  则b可表示成2进制数
b=((2^0)*c0) * a^((2^2)*c1) *...... * a^((2^(n-1)*c(n-1)),
a^2^i = (a^2^(i-1))^2,
则a^b可表示成
a^b = a^((2^0)*c0) * a^((2^2)*c1) *...... * a^((2^(n-1)*c(n-1))
a^b = (a^(2^0))^c0 * (a^(2^2))^c1 *...... * (a^(2^(n-1))^c(n-1)
其中ci 取值为0或1 (i >=0 && i < n) 

 

c语言程序代码

#include <stdio.h>
int power(int a, int b, int p)
{
    int ans = 1 % p;
    
    for (; b; b>>=1)
    {
        if(b & 1)
        {
            ans = (long long)ans * a % p;
        }
        
        a = (long long)a * a % p;    // a^(2^n)%p
    }

    return ans;
}

int main()
{
    printf("%d\n", power(5, 3, 4));
    return 0;
}

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部