ryo’s blog

日々学んだことをまとめています.

競プロ典型90問 020(★3) 浮動小数点の誤差

020 - Log Inequality(★3)

問題

 \log_2 a <  b \log_2 c が成り立つか。

解法

愚直に log() を使って求めると誤差が出てしまう。

そのため全て整数で処理をする必要がある。

対数 log は 底が同じ値の場合、log が外せるので、

\log_ax = \log_ayx = y と表せる。

そして累乗の場合は、

 b \log_a c = \log_a c ^ b が成り立つ。

後はこの公式を利用して、整数で比較すれば誤差なく答えが求まる。

所感

浮動小数点を扱う問題で特に制約の範囲が広い場合は要注意。

できるだけ怪しい浮動小数点演算は使わずに整数で計算した方が良さそう。

累乗も pow() だと誤差が出る場合もあるので、ループ処理で行うようにする。

コード

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
const int INF = (int)1e9;
const ll INFL = (ll)1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
int dx[]={0, 0, -1, 1};
int dy[]={1, -1, 0, 0};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main()
{
    ll a, b, c, x;
    cin >> a >> b >> c;

    x = c;
    rep(i,b - 1) x *= c;
    if (a < x) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}