perogram

pのk乗はoverflowするか?

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

f:id:peroon:20191001215508p:plain

// 底を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版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

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