結果

問題 No.2280 FizzBuzz Difference
コンテスト
ユーザー detteiuu
提出日時 2026-08-22 18:33:16
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 126 ms / 2,000 ms
+ 453µs
コード長 1,079 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 229 ms
コンパイル使用メモリ 96,108 KB
実行使用メモリ 85,588 KB
最終ジャッジ日時 2026-08-22 18:33:19
合計ジャッジ時間 3,024 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from sys import stdin
input = stdin.readline
from math import gcd, lcm

def inverse(n, d, MOD):
    return n * pow(d, -1, MOD) % MOD

def rangeModCount(l, r, c, m, k = 0):
    if l == r:
        return c if l%m == k else 0
    if c == 1: return -1

    if l > r: l, r = r, l
    if (r-l)%(c-1) != 0: return -1

    d = (r-l)//(c-1)

    GCD = gcd(m, d)
    if l%GCD != k%GCD: return 0
    ng = (k-l)//GCD
    mg = m//GCD
    dg = d//GCD
    f = inverse(ng, dg, mg)
    if c <= f:
        return 0
    else:
        return (c-f-1)//mg+1

for _ in range(int(input())):
    M, A, B, K = map(int, input().split())

    if A < K:
        print(0)
        continue
    if A == K:
        cntA = M//A
        cntB = M//B
        LCM = lcm(A, B)
        ans = (cntA-1)-cntB+M//LCM
        if M-(M-A)%A < M-(M-B)%B:
            ans += 1
        print(ans)
        continue

    l, r = K, A-K

    ans = rangeModCount(B, M-(M-B)%B, (M-(M-B)%B)//B, A, l)+rangeModCount(B, M-(M-B)%B, (M-(M-B)%B)//B, A, r)
    if M-(M-A)%A < M-(M-B)%B and (M-(M-B)%B)%A == r:
        ans -= 1

    print(ans)
0