pのk乗はoverflowするか？

• https://codeforces.com/contest/1228/problem/C
• この問題を解いていて、入力nが10¹⁸までなので、long longギリギリまで入力されうる
• pow(p, k)をナイーブに求めたらoverflowするし、modをとると正しく判定できない
• ということで判定関数を作った
• p^k > 10¹⁸ならoverflowと判定する。そのままpowしたら溢れるのでlogpを取って判定

// 底をpとしたlogp(n)
double logp(ll p, ll n){
  return log(n) / log(p);
}

// p^k is overflow ?
bool is_overflow(ll p, ll k){
  double a = logp(p, 1e18);
  if(k > a){
    return true;
  }else{
    return false;
  }
}

AC Code

https://codeforces.com/contest/1228/submission/61606338

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?