aoj number-theory

NTL_1_B | べき乗

NTL_1_B | べき乗
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B

2つの数XとNが与えられるので、XのN乗をもとめる.

解説

繰り返し自乗法という手法で計算量を約半分に出来る.

計算量

$$
O(\log N)
$$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define M 1000000007

Int X, Y;

Int faster_pow(Int x, Int y) {
  if (y == 0) return 1;
  Int res = faster_pow((x * x) % M, y / 2);
  if (y % 2 == 1) {
    res = (res * x) % M;
  }
  return res;
}

void input() {
  cin >> X >> Y;
}

void solve() {
  cout << faster_pow(X, Y) << endl;
}

int main() {
  input();
  solve();
  return 0;
}