読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ARC057 A - 2兆円

問題

問題概要

省略

解法

ループを回すだけ。一見、制約が大きいので回すだけではダメなように見えるが、金額は最低でも2倍に増えて行くので(k=1を除いて)、計算量がlogになり、時間内に可能。ただし、 k=1の場合は例外として処理する必要がある。

ミス

特になし。

コード

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdio>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
 
int main(void){
    ll a, k; cin >> a >> k;
    ll cnt = 0;
    //k=0場合だけ特別にやらないと計算量がすごいことに
    while(k == 0){
        printf("%lld\n", 2000000000000 - a);
        return 0;
    }
    while(a < 2000000000000){
        ll now = a;
        a += 1 + k * now;
        cnt++;
    }
    printf("%lld\n", cnt);
    return 0;
}