結果

問題 No.2280 FizzBuzz Difference
ユーザー sotanishy
提出日時 2023-04-21 23:38:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 136 ms / 2,000 ms
コード長 1,281 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 82,000 KB
実行使用メモリ 77,620 KB
最終ジャッジ日時 2024-11-06 16:56:38
合計ジャッジ時間 1,607 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


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

    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())
    g = gcd(A, B)

    if K % g != 0 or K > A:
        print(0)
        continue

    M //= g
    A //= g
    B //= g
    K //= g

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

    if A == K:
        C = M//A-1
        lcm = A*B//gcd(A, B)
        cntBnotA = M//B - M//lcm
        cnt_all = M//A + cntBnotA
        ans = cnt_all - 1 - 2*cntBnotA
        if M % B < M % A:
            ans += 1
        print(ans)
        continue

    ans = calc(A, B, K, M) + calc(B, A, K, M)
    print(ans)
0