【競プロ】整数の整数乗

ここでは、 $10^9$ や $2^3$ などの、整数の整数乗について見ていきます。競プロ 記事の一覧はこちら

【広告】

整数の自然数乗

$1$ に同じ整数を何回か掛けてみます。

#include <iostream>
using namespace std;

int main() {
  int ans = 1, a = 3, b = 4;
  for (int i = 0; i < b; i++) ans *= a;
  cout << ans; // 81
  return 0;
}

上の計算では、 $3$ を $4$ 回掛けているので、 $3\times3\times3\times3=81$ を掛けてことになります。このように、同じものを何度も掛ける計算を、「 $a$ を $b$ 乗する」「 $a$ の $b$ 乗」といいます。この計算をべき乗(exponentiation) といいます。また、 $3$ の部分を底(てい)、 $4$ の部分を指数といいます。

数学の世界では、「 $a$ の $b$ 乗」を $a^b$ と表します。競プロでは、次のような条件式でよく見かけます。\[ 1\leqq N\leqq 10^9 \]この場合、 $N$ は、10を9回掛けた数以下だということです。10を9回掛けてできる数は、0が9個続いてその左に1が来る数なので、10桁の数となります。

コードでのべき乗の表し方は、言語によってバラバラです。C++の場合は次のように書きます。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
  int a = 3, b = 4;
  cout << pow(a, b); // 81
  return 0;
}

べき乗を表す演算子はなく、cmath をインクルードして pow関数を使います。一方、Pythonでは次のように書きます。

a, b = 3, 4
print(a ** b)

ぜんぜん違いますね。言語によっては、この**という演算子が用意されていることもあります。

$\TeX$ では、べき乗を表すときに^という記号を使いますが、プログラミングの世界では、これはビット演算を表し、べき乗を表さないことが多いので注意しましょう。

【広告】

C++では、10のべき乗には特別な表し方があります。 2e3 とかくと、 $2\times 10^3$ のことになります。競プロでは、「答えを $10^9+7$ で割った余りを求めなさい」という出題のされ方がよくされますが、この $10^9+7$ は、C++では、1e9 + 7と書くことができます。

前に、11の9乗を計算するためにpow(11, 9)と書いたら、2.35795e+009と表示されてしまうことを見ました(参考:【競プロ】数#数の出力)。これは、 $2.35795$ に、 $10^9$ を掛けた数である、ということです(下の方の桁は捨てられています)。9回掛けただけで、int型からあふれる大きな数になっていることがわかります。

べき乗は、値がすぐに大きくなってしまいます。オーバーフローしてしまうことがあるので、競プロでは、べき乗を表す関数はあまり使われません。ではどうするかは、将来、余りの計算のところで見ることになります。

10のべき乗と2のべき乗

べき乗の中では、10のべき乗がよく使われます。10のべき乗は、数字が何桁かを表すのにとても便利です。 $10^5$ なら、 $0$ が5つ並ぶことから6桁の数だとわかります。 $100000$ と書かれるよりも見やすいですね。先ほども書きましたが、競プロでは、条件式などでよく使われます。

また、2のべき乗が使われることもあります。 $2^{30}$ であれば、 $2$ を30回掛けたものです。これがどれくらいの値なのか、何桁くらいの数なのかは少しわかりづらいですね。

しかし、次のように考えるとわかりやすくなります。 $2$ を何度も掛けていくと、 $2^{10}=1024$ だと計算できます。だいたい $1000$ です。そのため、 $2^{10}$ はだいたい $10^3$ くらいだといえます。

$2^{30}$ は、 $2$ を30回掛けたものなので、 $2^{10}\times 2^{10}\times 2^{10}$ と書けます。10回の3セットにしたわけです。こうすると、 $10^3$ を3回掛けたものとだいたい同じであることがわかります。つまり、だいたい $10^9$ くらいだな、と概算できます。int型にも収まるくらいの値だな、とわかりますね(実際、収まります)。

このint型ですが、扱える値の範囲は、-2147483648 ~ 2147483647 でした。どこから出てきたかわかりにくい数字ですが、これを2のべき乗を使った表すと、 $-2^{31}$ ~ $2^{31}-1$ となります。また、long long int型は、-9223372036854775808 ~ 9223372036854775807 でしたが、これも2のべき乗を使うと、 $-2^{63}$ ~ $2^{63}-1$ となります。2のべき乗を使えばシンプルに表せる数字だったんですね。

2のべき乗は競プロの問題文にもよく出てくるので、何桁くらいの値なのか、計算できるようになっておくと役立ちます。 $2^{10}$ が $10^3$ とだいたい同じであることを利用しましょう。

2乗

ある数を2乗すること、つまり、2回掛けることを、平方や自乗といいます。また、ある数が、ある整数の2乗となっている場合、その数を平方数(square number) といいます。例えば、 $2^2=4$, $3^2=9$, $10^2=100$ なので、 $4,9,100$ はいずれも平方数です。

平方数が出てくる問題には、AtCoder ABC 077 B – Around Squareなどがあります。

【広告】

負の整数乗

負の整数乗、つまり、 $10$ の $-3$ 乗のようなものもあります。例えば、AtCoder ABC 117 A – Entrance Examinationの出力の部分に、「誤差が $10^{-3}$ 以下であれば」という文があります。このべき乗はどのように計算するか、見ていきましょう。

負の整数の計算では、徐々に値を減らしていったときに答えがどう変化するかを見てきました(参考:【競プロ】整数の掛け算)。今回も同じ手法を使います。

$10^3$ から、3乗、2乗、1乗と減らしていくと、答えは桁が1つずつ減っていきます。そのため、マイナス乗は次のように計算します。
\begin{eqnarray}
10^3 &=& 1000 \\[5pt] 10^2 &=& 100 \\[5pt] 10^1 &=& 10 \\[5pt] 10^0 &=& 1 \\[5pt] 10^{-1} &=& 0.1 \\[5pt] 10^{-2} &=& 0.01 \\[5pt] 10^{-3} &=& 0.001 \\[5pt] \end{eqnarray}0乗は1となり、マイナス乗をしていくと、 $1$ がどんどん右へと移動していきます。

$2$ の場合は、3乗、2乗、1乗と減らしていくと、値が半分になっていくので、マイナス乗も同じように計算していきます。
\begin{eqnarray}
2^3 &=& 8 \\[5pt] 2^2 &=& 4 \\[5pt] 2^1 &=& 2 \\[5pt] 2^0 &=& 1 \\[5pt] 2^{-1} &=& 0.5 \\[5pt] 2^{-2} &=& 0.25 \\[5pt] 2^{-3} &=& 0.125 \\[5pt] \end{eqnarray}0乗は1となり、マイナス乗は半分ずつとなるように計算します。

0乗が1になることを不思議に思う人もいるかもしれません。ただ、0乗を、「0回掛ける」=「何も掛けない」=「掛けても何も効果がない」と考えると、0乗が1になることもわかりやすいのではないかと思います。

上で見た計算をコードで確かめてみましょう。C++で、 $2$ と $10$ のべき乗の計算結果を出力してみます。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
  for (int i = 3; i >=-3; i--) {
    cout << i << ": " << pow(10, i) << "\n";
  }
  cout << "\n";
  for (int i = 3; i >=-3; i--) {
    cout << i << ": " << pow(2, i) << "\n";
  }
  return 0;
}

上で見た結果と同じものが得られることがわかるでしょう。

一般に、 $a,b$ が正の数であるとき、 $a^{-b}$ は、 $a^b$ で割ることと一致します。また、 $\dfrac{1}{a^b}$ とも言い換えられます。ただ、当面は、 $a=2,10$ の場合がわかっていれば、問題ないでしょう。

おわりに

ここでは、整数のべき乗について見てきました。 $a^b$ が $a$ を $b$ 回掛けたものであることや $b$ が負の整数のときの扱いがわかっていれば、当面問題を解くときには困らないでしょう。

高校生向けの記事ですが、数学として学びたい場合は、【基本】整数の指数が参考になると思います。