0\le a,b <2^{31},2\le p < 2^{31} (快速幂/取模公式) P1226
1\le a\le10^9,1\le b\le10^{2\times10^7},1\le m\le 10^8 (欧拉函数/拓展欧拉定理) P5091
20分代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
ll a, b = 0, r = 1, p = 1e9 + 7;
cin >> a;
ll t = p, phi = p;
for (ll i = 2; i * i <= p; ++i)
{
if (t % i == 0)
{
phi = phi - phi / i;
while (t % i == 0)
{
t /= i;
}
}
}
if (t > 1)
{
phi = phi - phi / t;
}
char c;
bool flag = false;
while (cin >> c)
{
b = b * 10 + (c - '0');
if (b >= phi)
{
flag = true;
b %= phi;
}
}
if (flag)
{
b += phi;
}
for (; b; b >>= 1, a = a * a % p)
{
if (b & 1)
{
r = r * a % p;
}
}
cout << r;
return 0;
}
12分代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
ll a, b, r = 1, p = 1e9 + 7;
cin >> a >> b;
for (; b; b >>= 1, a = a * a % p)
{
if (b & 1)
{
r = r * a % p;
}
}
cout << r;
return 0;
}
4分代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
ll a, b, r = 1, p = 1e9 + 7;
cin >> a >> b;
while (b--)
{
r *= a;
}
cout << r;
return 0;
}