blog

About me

Archives

Tags

精進メモ：AtCoder Beginner Contest 180 D - Takahashi Unevolved

Nov 05, 2020, 15:55 #Procon

問題：AtCoder Beginner Contest 180 D - Takahashi Unevolved

Difficulty: 721

解説 AC。方針は正しかったがオーバーフローのチェックをしていなかった。

WA

// C
#include <stdio.h>

int main(void) {
    long long x, y, a, b;
    scanf("%lld %lld %lld %lld", &x, &y, &a, &b);

    long long ans = 0;
    while (a * x <= x + b && a * x < y) {
        x *= a;
        ans++;
    }
    ans += (y - 1 - x) / b;

    printf("%lld\n", ans);
    return 0;
}

入力が 1 <= X < Y <= 1e18 と大きいので、while の条件式でオーバーフローが発生してしまっていた。

a * x を double にキャストしてから 2e18 と比べてオーバーフローしていないかチェックすることで解決。

AC

// C
#include <stdio.h>

int main(void) {
    long long x, y, a, b;
    scanf("%lld %lld %lld %lld", &x, &y, &a, &b);

    long long ans = 0;
    while ((double) a * x <= 2e18 && a * x <= x + b && a * x < y) {
        x *= a;
        ans++;
    }
    ans += (y - 1 - x) / b;

    printf("%lld\n", ans);
    return 0;
}

Tweet