結果

問題 No.2280 FizzBuzz Difference
ユーザー tamatotamato
提出日時 2023-04-21 23:08:20
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,337 bytes
コンパイル時間 684 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 79,240 KB
最終ジャッジ日時 2024-04-24 09:09:04
合計ジャッジ時間 8,913 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
57,600 KB
testcase_01 WA -
testcase_02 AC 1,432 ms
78,076 KB
testcase_03 WA -
testcase_04 AC 1,703 ms
78,772 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
mod = 998244353
from math import gcd


def PrimeDecomposition(N):
    ret = {}
    n = int(N ** 0.5)
    for d in range(2, n + 1):
        while N % d == 0:
            if d not in ret:
                ret[d] = 1
            else:
                ret[d] += 1
            N //= d
        if N == 1:
            break
    if N != 1:
        ret[N] = 1
    return ret


def euler_phi(N):
    P = PrimeDecomposition(N)
    ret = N
    for p in P:
        ret = ret * (p - 1) // p
    return ret


for _ in range(int(input())):
    M, A, B, K = map(int, input().split())
    if K > A:
        print(0)
        continue

    g = gcd(A, B)
    A //= g
    B //= g
    M //= g
    if K % g:
        print(0)
        continue
    K //= g

    phi = euler_phi(A)
    X = B % A
    X_inv = pow(X, phi - 1, A)

    if K == A:
        ans = (M // (A * B)) * (B - A + 1) - 1
        m = M % (A * B)
        ans += m // A - (m // B) * 2
        a_max = (m // A) * A
        b_max = (m // B) * B
        if b_max > a_max:
            ans += 2
        print(ans)
    else:
        ans = (M // (A * B)) * 2
        i = (K * X_inv) % A
        if M % (A * B) >= B * i:
            ans += 1
        j = ((A - K) * X_inv) % A
        if M % (A * B) >= ((B * j - 1) // A + 1) * A:
            ans += 1
        print(ans)
0