結果

問題 No.2280 FizzBuzz Difference
ユーザー tamato
提出日時 2023-04-21 23:12:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,648 ms / 2,000 ms
コード長 1,333 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 79,292 KB
最終ジャッジ日時 2024-11-25 00:24:08
合計ジャッジ時間 9,242 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

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)
        a_max = (m // A) * A
        b_max = (m // B) * B
        if b_max > a_max:
            ans += 1
        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