快速幂算法总结

2024-01-08 23:34:09

知识概览

  • 快速幂可以在O(logk)的时间复杂度之内求出来a^k \ mod \ p的结果。(1\leqslant a,p,k\leqslant 10^9)

?

例题展示

快速幂

题目链接

活动 - AcWing 系统讲解常用算法与数据结构，给出相应代码模板，并会布置、讲解相应的基础算法题目。icon-default.png?t=N7T8https://www.acwing.com/problem/content/877/

代码
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);
        
        printf("%d\n", qmi(a, k, p));
    }
    
    return 0;
}

快速幂求逆元

题目链接

活动 - AcWing 系统讲解常用算法与数据结构，给出相应代码模板，并会布置、讲解相应的基础算法题目。icon-default.png?t=N7T8https://www.acwing.com/problem/content/878/

题解

由费马小定理，可得当p为质数时，a^{p-2}为a的乘法逆元，本题求a^{p-2}模p的值。

代码
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int a, p;
        scanf("%d%d", &a, &p);
        
        int res = qmi(a, p - 2, p);
        if (a % p) printf("%d\n", res);
        else puts("impossible");
    }
    
    return 0;
}

参考资料

  1. AcWing算法基础课

文章来源:https://blog.csdn.net/u012181348/article/details/135467533
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。