专业上海网站建设,手机网站插件代码,如何发布视频赚钱,线下推广100种方式知识概览 快速幂可以在O(logk)的时间复杂度之内求出来的结果。 例题展示
快速幂
题目链接
活动 - AcWing 系统讲解常用算法与数据结构#xff0c;给出相应代码模板#xff0c;并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/877/
代码
#inc…知识概览 快速幂可以在O(logk)的时间复杂度之内求出来的结果。 例题展示
快速幂
题目链接
活动 - AcWing 系统讲解常用算法与数据结构给出相应代码模板并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/877/
代码
#include iostream
#include algorithmusing 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 系统讲解常用算法与数据结构给出相应代码模板并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/878/
题解 由费马小定理可得当p为质数时为a的乘法逆元本题求模p的值。 代码
#include iostream
#include algorithmusing 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;
} 参考资料
AcWing算法基础课
