欧拉降幂模板
作者:
冰冷酒
,
2022-04-03 13:34:11
,
所有人可见
,
阅读 259
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1000010;
LL x, p;
char y[N];
LL qmi(LL a, LL k, LL p)
{
LL res = 1;
a %= p;
while (k)
{
if(k & 1)
res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
LL oula(LL x)
{
LL num = x;
for(LL i = 2; i <= x / i; i ++)
{
if(x % i == 0)
{
num = num / i * (i - 1);
while(x % i == 0)
x /= i;
}
}
if(x > 1) num = num / x * (x - 1);
return num;
}
LL oulami(LL a, char b[], LL c)
{
LL num = oula(c);
LL mi = 0;
LL n = strlen(b);
for(LL i = 0; i < n; i ++)
{
mi = (mi * 10 + b[i] - '0') % num;
}
mi += num;
return qmi(a, mi, c);
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --)
{
cin >> x >> y >> p;
if (x == 0 && y[0] == '0')
cout << "1" << '\n';
else
cout << (LL)oulami(x, y, p) << '\n';
}
return 0;
}
可是可是,不加y[0] = ‘0’ 的特判过不去哦
x=0, y=0的时候是1,但是输出0了
√,这个点wa了好多发,这边 忘记改了
难怪当时照搬wa了几发hh
找大数乘法那题,找到这里了
我也是因为那题整理的哈哈哈
哈哈,知道,那个foceless是我高中同学,你应该还认识他
hhh我也是