B - rng_10s AtCoder Grand Contest 026

B - rng_10s

問題概略

はじめAがある。そこからBを引き、もしC以下ならD追加する

何回操作を繰り返しても数がマイナスにならなければYes 

制約

• $1\le T\le 300$
• $1\le A,B,C,D\le {10}^{18}$
• 入力される値は全て整数である

解法

まず、AがBより小さい時は死ぬ

DがBより小さいときも補充が追いつかないので死ぬ。

BがC以下ならば、補充は間に合うので続く。

また、一日が終わった際に残りがB未満に出来るなら死ぬ事がわかる。

この時、補充されていないことからC < ? < Bを満たせばよい。

-Bと+Dを複数回繰り返す事でg = gcd(B,D)の倍数を作ることが出来る。

そのため、任意の整数zについてA%g + g * z が作れる

C< ? < Bを満たすzが存在すれば途中で死ぬし、違うなら無限に続く。

類題

D - Bus Tour

↑これの解説を見たら理解できました

static void Solve()
{
    N = NI();
    for (int i = 0; i < N; i++)
    {
    long A = NL();
    long B = NL();
    long C = NL();
    long D = NL();
    if (A < B || D < B )
    {
        Console.WriteLine("No"); continue;
    }
    else if (C >= B)
    {
        Console.WriteLine("Yes"); continue;
    }
    //C < ? < B,D を満たす?を作れるなら死ぬ
    long g = Gcd(B, D);
    long a = A % g;
    //a + gpしか作れない
    //Cより大きく最小の数
    long upc = a + Ceil(C - a + 1, g) * g;
    if (C < upc && upc < B && upc < D)
    {
        Console.WriteLine("No");
    }
    else
    {
        Console.WriteLine("Yes");
    }
    }
}