开发者社区人工智能文章正文

快速幂算法

2023-05-09 6668

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 什么是快速幂呢？就是更快速的计算幂运算。

什么是快速幂呢？就是更快速的计算幂运算。

875. 快速幂 - AcWing题库

快速幂的作用就是跟题目中描述的一样

先预处理出这些值

比如

求k的个位

k&1

删除k的个位

k>>=1

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;//b的个位如果是1
        a = a * (LL)a % p;
        b >>=1;//也可以写成b/=2
    }
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%lld\n", qmi(a, b, p));
    }
    return 0;
}