結果

問題 No.2280 FizzBuzz Difference
コンテスト
ユーザー sotanishy
提出日時 2023-04-21 23:17:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,484 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 78,752 KB
最終ジャッジ日時 2024-11-06 16:41:54
合計ジャッジ時間 1,956 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


def floor_sum(n, m, a, b):
    s = 0
    if a >= m:
        s += (a // m) * n * (n - 1) // 2
        a %= m
    if b >= m:
        s += (b // m) * n
        b %= m
    y = (a * n + b) // m
    if y == 0:
        return s
    x = (m * y - b + a - 1) // a
    s += (n - x) * y + floor_sum(y, a, m, a * x - m * y + b)
    return s


def extgcd(a, b):
    s, sx, sy, t, tx, ty = a, 1, 0, b, 0, 1
    while t:
        q = s // t
        s -= t * q
        s, t = t, s
        sx -= tx * q
        sx, tx = tx, sx
        sy -= ty * q
        sy, ty = ty, sy
    return sx, sy


def calc(A, B, K, M):
    # find the number of (x,y)
    # such that Ax+K=By
    # and 1 <= x <= M/A
    # and 1 <= y <= M/B

    g = gcd(A, B)
    if K % g != 0:
        return 0
    A //= g
    B //= g
    K //= g

    x0, y0 = extgcd(-A, B)
    x0 *= K
    y0 *= K

    # x = x0 + Bt
    # y= y0 + At

    tmin = max((1-x0+B-1)//B, (1-y0+A-1)//A)
    tmax = min((M//A-x0)//B, (M//B-y0)//A)
    return max(0, tmax-tmin+1)


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

    if K > A:
        print(0)
        continue

    if B % A == 0:
        if K == A:
            print(M//A-1)
        else:
            print(0)
        continue

    ans = 0

    if A == K:
        C = M//A-1
        ans += C - floor_sum(C, B, A, 2*A) + floor_sum(C, B, A, A-1)
    ans += calc(A, B, K, M) + calc(B, A, K, M)
    print(ans)
0