快速幂
输入样例
2
3 2 5
4 3 9
输出样例
4
1
代码
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include <stdbool.h>
#define ll long long
ll int quick_pow(ll int a, ll int b, ll int p)
{
ll int ans = 1, base = a;//base是每一位的次幂,ans是所求结果
while (b != 0)
{
if (b & 1) //按位与1表示b是奇数(最后一位二进制位是1)
ans = ans * base % p; //ans与对应的幂相乘取模
base = base * base % p; //计算下一位的次幂结果
b >>= 1; //右移,表示舍弃最后一位二进制位
}
return ans;
}
int main()
{
int n;
ll int a, b, p;
scanf("%d", &n);
while (n--)
{
scanf("%lld%lld%lld", &a, &b, &p);
printf("%lld\n", quick_pow(a,b,p));
}
return 0;
}
快速幂求逆元
样例
3
4 3
8 5
6 3
样例
1
2
impossible
快速幂+费马小定理
代码
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include <stdbool.h>
#define ll long long
/*快速幂的模板*/
ll int inverse(ll int a, ll int b, ll int p)
{
ll int ans = 1, base = a;
while (b != 0)
{
if (b & 1)
ans = ans * base % p;
base = base * base % p;
b >>= 1;
}
return ans%p;
}
int main()
{
int n;
ll int a, p;
scanf("%d", &n);
while (n--)
{
scanf("%lld%lld", &a, &p);
/*费马小定理的应用*/
if (a % p != 0) //如果a是p的倍数,那么a%p一定为0
printf("%lld\n", inverse(a, p - 2, p));
/* a^(p-1)=1(mod p) */
/* a*a^(p-2)=1(mod p) */
else
printf("impossible\n");
}
return 0;
}
矩阵快速幂
代码
void mul(LL a[][N],LL b[][N])
{
memset(temp, 0, sizeof(temp));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
temp[i][j] = (temp[i][j] + a[i][k] * b[k][j] % mod) % mod;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
a[i][j] = temp[i][j];
return;
}
void quick_pow(int b)
{
memset(res, 0, sizeof (res));
for (int i = 0; i < n; i++)
res[i][i] = 1;
while (b != 0)
{
if (b & 1)
mul(res, a);
mul(a, a);
b = b >> 1;
}
return;
}