【AtCoder】C++のpowに苦しめられた話

11月4日に開催されたAtCoder Beginner Contest 327にて、B問題のA^Aに苦しめられた話です。
ちなみに結果はAとC問題を解いて350点でした！（Bを解いていれば、、）

https://atcoder.jp/contests/abc327

内容

以下が問題内容です。

整数Bが与えられます。
A^A =B であるような正の整数Aが存在するならばその値を、存在しないならば-1を出力してください。

非常にシンプルですね。
問題の制約では、Bの上限は10^18でしたので、A^Aが初めて10^18を超える整数-1がAの上限となるので、それを全探索で求めればいける！と思いました。

計算してみると16^16 = 1.8446744e+19だったので、Aの上限は15と決定し早速コーディングへ。

提出コード（WAあり）

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, init, n) for (int i = init; i < (int)(n); i++)
using ll = long long;
using Graph = vector<vector<int>>;

int main()
{
  ll b;
  cin >> b;

  repi(i, 1, 16) {
    if (pow(i,i) == b) {
      cout << i << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

冪乗の計算だからpow使って終わりだ！と思っていたら、

そこから数回提出し直しましたが結局ACできず、C問題へ、

TimeUp

ACできなかった原因

原因はpowでした。
pow関数を使用すると浮動小数点数型に起因する誤差が発生するようです。

https://atcoder.jp/contests/abc327/editorial/7567

試しに15^15を計算してみると誤差が確認できます。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;

int main()
{
  ll x = pow(15, 15);
  ll y = 1;
  rep(i, 15) y *= 15;

  cout << x << endl;
  cout << y << endl;
}

output

437893890380859392
437893890380859375 <-- こっちが正しい

提出コード（AC）

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, init, n) for (int i = init; i < (int)(n); i++)
using ll = long long;
using Graph = vector<vector<int>>;

int main()
{
  ll b;
  cin >> b;

  repi(a, 1, 16) {
    ll x = 1;
    rep(i, a) x *= a;
    if (x == b) {
      cout << a << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

pow関数を使用せずrep(i, a) x *= a;で冪乗の計算を実現しています。

まとめ

powには気をつけましょう！