Problem Description 题目链接 http://acm.fzu.edu.cn/problem.php?pid=1752
Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,B,C<2^63).
Input
There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.
Output
For each testcase, output an integer, denotes the result of A^B mod C.
Sample Input
3 2 4
2 10 1000
Sample Output
- 1
- 24
- #include <iostream>
- #include <stdio.h>
- using namespace std;
- typedef long long LL;
- /*
- 这道题有个大坑 如果直用快速幂 LL 会爆 必须配合快速乘 其中快速乘如果 %= 还是会超时 使用 -= 会快点
- 思路: 快速幂 + 快速乘
- */
- // 快速乘
- LL quickMul(LL a, LL b, LL mod) {
- LL res = 0;
- while (b)
- {
- if (b & 1) {
- res += a;
- // 注意 %= 还得用快速求余 于是干脆用 -=
- if (res>= mod)
- res -= mod; // 大于减 mod
- }
- a <<= 1;
- if (a>= mod)
- a -= mod;
- b>>= 1;
- }
- return res;
- }
- // 快速幂
- LL quickPow(LL a, LL b, LL mod)
- {
- LL res = 1;
- a %= mod;
- while (b)
- {
- if (b & 1) {
- res = quickMul(res, b, mod);
- }
- b>>= 1;
- a = quickMul(a, a, mod);
- }
- return res;
- }
- int main()
- {
- LL a, b, c, res;
- while (~scanf("%I64d%I64d%I64d", &a, &b, &c))
- {
- // 注意快速幂 以及 LL 的时候快速乘
- a %= c;
- res = 1;
- while (b)
- {
- if (b & 1)
- res = quickMul(res, a, c);
- b = b>> 1;
- a = quickMul(a, a, c);
- }
- printf("%I64d\n", res);
- }
- }
来源: http://www.bubuko.com/infodetail-3518236.html