Colton Star Blog

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
int a, b, p;
5
int po(int x, int y)
6
{
7
    if (y == 0)
8
        return 1;
9
    if (y == 1)
10
        return x;
11
    if (y % 2 == 0)
12
        return (po(x, y / 2) % p) * (po(x, y / 2) % p);
13
    else
14
        return (po(x, y / 2) % p) * (po(x, y / 2) % p) * (x % p);
15
}
16
signed main()
17
{
18
    cin >> a >> b >> p;
19
    int ans=po(a, b) % p;
20
    printf("%lld^%lld mod %lld=%lld", a, b, p, ans);
21
}

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
int a, b, p;
5
int po(int x, int y)
6
{
7
    if (y == 0)
8
        return 1;
9
    if (y == 1)
10
        return x%p;
11
    int half = po(x, y / 2) % p;
12
    if (y % 2 == 0)
13
        return (half*half % p);
14
    else
15
        return half*half * (x % p)%p;//注意这里half完了也要取模，这段代码没取是错的
16
}
17
signed main()
18
{
19
    cin >> a >> b >> p;
20
    int ans=po(a, b) % p;
21
    printf("%lld^%lld mod %lld=%lld", a, b, p, ans);
22
}

1
int quickpower(int a,int b,int p){
2
  int res=1%p;
3
  while(b){
4
    if(b&1)res=res*a%p;
5
    a=a*a%p;
6
    b>>=1;
7
  }
8
  return res;
9
}
10
//可__int128优化