結果

問題 No.3398 Accuracy of Integer Division Approximate Function 2
コンテスト
ユーザー Kude
提出日時 2025-12-05 02:56:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 256 ms / 2,000 ms
コード長 2,343 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 283 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 78,556 KB
最終ジャッジ日時 2025-12-05 02:56:38
合計ジャッジ時間 3,959 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import gcd
def floor_sum(n, m, a, b):
    ans = 0
    while True:
        if a < 0 or a >= m:
            k = a // m
            a = a % m
            if a < 0:
                a += m
                k -= 1
            ans += k * n * (n - 1) // 2
        if b < 0 or b >= m:
            k = b // m
            b = b % m
            if b < 0:
                b += m
                k -= 1
            ans += k * n
        y_max = (a * n + b) // m
        if y_max == 0:
            break
        x_max = y_max * m - b
        ans += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, (a - x_max % a) % a
    return ans

def ceil_div(p, q):
    return (p - 1) // q + 1

def solve(d, a, b, k):
    k += 1
    # y=floor((ax+a-1)/d)
    # y=floor(ex/b)
    e = a * b // d
    def get_min_x(c):
        # y=(ax+c)/d
        # y=ex/b
        # a/d == e/b
        if c // d >= k:
            return 0
        # print(a, d, e, b, c)
        if a * b == e * d:
            if c // d + (c % d >= gcd(a, d)) < k:
                return -1
            x_from = 0
        else:
            x_from = max(0, ceil_div(b * (d * (k - 1) - c), a * b - d * e))
        # y=(a(xfrom+x)+c)/d - k
        # y=e(x_from+x)/b
        # print(c)
        c += x_from * a - d * k
        f = e * x_from
        # y=(ax+c)/d
        # y=(ex+f)/b
        def check(n):
            return floor_sum(n, d, a, c) - floor_sum(n, b, e, f) != -n
        l = 0
        r = 1
        while not check(r):
            l = r
            r *= 2
            # print(mode,a * b == e * d,d,a,c,b,e,f)
        # print('a',a,l,r, x_from)
        # print(floor_sum(r, d, a, c), floor_sum(r, b, e, f))
        while r - l > 1:
            mid = (l + r) // 2
            if check(mid):
                r = mid
            else:
                l = mid
        return x_from + l
    xmin = get_min_x(a - 1)
    # print(xmin)
    if xmin == -1:
        return -1
    l = -1
    r = a - 1
    # print(l,r)
    while r - l > 1:
        mid = (l + r) // 2
        if (a * xmin + mid) // d - e * xmin // b >= k:
            # print('ok',mid)
            r = mid
        else:
            l = mid
    # print(a, xmin, r, (a * xmin + mid) // d, e * xmin // d, k)
    return a * xmin + r

for _ in range(int(input())):
    print(solve(*map(int, input().split())))
    # exit()
0