免费网站建设itcask_莱芜买房网站_拼多多跨境电商平台_优化营商环境建议

目录

题目：

分析：

代码：

---

题目：

给定 n 组 ai,bi,pi，对于每组数据，求出 (ai^bi)mod pi 的值。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含三个整数 ai,bi,pi。

输出格式

对于每组数据，输出一个结果，表示 (ai^bi)mod pi 的值。

每个结果占一行。

数据范围

1≤n≤100000，
1≤ai,bi,pi≤2×10^9

时/空限制：

1.5s / 64MB

输入样例：

2
3 2 5
4 3 9

输出样例：

4
1

分析：

一、首先我们需要了解一下关于取余的公式:
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p ) % p
(a * b) % p = (a % p * b % p) % p 

二、反复平方法（二进制）
例如：现在要求 a^11%p

a^11(10)=a^1011(2)

二进制1011 = 2^3*1 + 2^2*0 + 2^1*1 + 2^0*1,所以a^11=a^(2^3*1 + 2^2*0 + 2^1*1 + 2^0*1)
=a^(2^3*1) * a^(2^2*0) * a^(2^1*1) * a^(2^0*1) = a^(2^3*1) * a^(2^1*1) * a^(2^0*1)
所以(a^11)%p = (a^(2^3*1) * a^(2^1*1) * a^(2^0*1))%p
={[a^(2^3*1)]%p * [a^(2^1*1)]%p * [a^(2^0*1)]%p}%p
所以就只用分别求出[a^(2^3*1)]%p、[a^(2^1*1)]%p、[a^(2^0*1)]%p，再相乘，最后%p即可

代码：

#include <iostream>using namespace std;typedef long long LL; // 10^9*10^9要用LL（a*a可能出现的情况）LL qmi(int a, int b, int p)
{LL res = 1 % p;while (b){if (b & 1)  //二进制下指数的末位是1的时候，则要进入if循环，进行反复平方相乘//例如1001的当前计算位就是1， 100*1* 星号中的1就是当前计算使用的位res = res * a % p; //累乘当前项并存储（第一次迭代的时候，a的2的0次方就是a）a = a * (LL)a % p;//计算要相乘的下一项，例如当前是n^2的话计算下一项n^2的值//n^4 = n^2 * n^2;b >>= 1; //指数位右移一位，把末位删掉，为下一次运算做准备//一次的右移将舍弃一个位例如1011(2)一次左移后变成101(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;
}