DEV

C++ 累乗の速いやつ

#C++#アルゴリズム#数学

https://blog.logicky.com/2017/01/30/python3-%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%EF%BC%88%E7%B4%AF%E4%B9%97%EF%BC%89%E3%83%BB%E8%A8%88%E7%AE%97%E9%87%8F/ — blog.logicky.com

上記でPythonでやっていますが、C++でもやってみます。どうも速いやつは「繰り返し二乗（自乗）法」という名前らしい。

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using LL = long long;


// xのn乗
LL powpow(LL x, LL n) {
  if (n == 0) return 1;
  LL val = powpow(x, n / 2);
  val *= val;
  if (n % 2 == 1) val *= x;
  return val;
}


int main() {
  cout << powpow(10, 18) << endl;
}

C++にはpowという関数があるので、基本的にそれを使えばいいはずなんだけど、競プロだと超大きい数字の累乗を出してそれを超大きい数字で割った余りを出したりするので、そういうときに使えるのじゃ。

割って余りだすやつ

大きい数字を扱う前提で考えますと、累乗計算が終わってから割ろうとすると、累乗計算の途中でキャパオーバーになっちゃって不本意な数字になっちゃうリスクがあります。そこで、掛け算する度に割って余りを出すようにします。

サンプルコード

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9+7;


// xのn乗
LL powMod(LL x, LL n) {
  if (n == 0) return 1 % MOD;
  LL val = powMod(x, n / 2);
  val *= val;
  if (n % 2 == 1) val *= x;
  return val % MOD;
}


int main() {
  cout << powMod(10, 18) << endl;
}

結果

49