結果

問題 No.2280 FizzBuzz Difference
ユーザー sotanishysotanishy
提出日時 2023-04-21 23:37:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 142 ms / 2,000 ms
コード長 1,164 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 77,696 KB
最終ジャッジ日時 2024-04-24 09:31:06
合計ジャッジ時間 1,685 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
52,480 KB
testcase_01 AC 138 ms
77,312 KB
testcase_02 AC 129 ms
76,928 KB
testcase_03 AC 100 ms
76,160 KB
testcase_04 AC 132 ms
77,696 KB
testcase_05 AC 121 ms
77,184 KB
testcase_06 AC 130 ms
76,928 KB
testcase_07 AC 142 ms
77,568 KB
権限があれば一括ダウンロードができます

ソースコード

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 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