結果

問題 No.2066 Simple Math !
ユーザー shotoyooshotoyoo
提出日時 2022-09-03 13:41:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,230 ms / 2,000 ms
コード長 2,156 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 81,408 KB
最終ジャッジ日時 2024-04-28 12:10:00
合計ジャッジ時間 25,953 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
54,656 KB
testcase_01 AC 90 ms
77,056 KB
testcase_02 AC 121 ms
77,356 KB
testcase_03 AC 94 ms
77,056 KB
testcase_04 AC 1,222 ms
81,408 KB
testcase_05 AC 1,160 ms
80,128 KB
testcase_06 AC 902 ms
79,488 KB
testcase_07 AC 1,180 ms
80,640 KB
testcase_08 AC 1,230 ms
81,408 KB
testcase_09 AC 1,030 ms
80,512 KB
testcase_10 AC 1,167 ms
80,512 KB
testcase_11 AC 1,157 ms
80,512 KB
testcase_12 AC 881 ms
78,848 KB
testcase_13 AC 1,185 ms
80,256 KB
testcase_14 AC 1,056 ms
80,384 KB
testcase_15 AC 1,034 ms
79,744 KB
testcase_16 AC 791 ms
79,104 KB
testcase_17 AC 1,029 ms
80,000 KB
testcase_18 AC 1,054 ms
79,872 KB
testcase_19 AC 572 ms
78,848 KB
testcase_20 AC 705 ms
79,488 KB
testcase_21 AC 710 ms
79,744 KB
testcase_22 AC 733 ms
79,232 KB
testcase_23 AC 596 ms
79,104 KB
testcase_24 AC 764 ms
79,360 KB
testcase_25 AC 805 ms
78,848 KB
testcase_26 AC 736 ms
78,848 KB
testcase_27 AC 966 ms
80,512 KB
testcase_28 AC 966 ms
79,744 KB
testcase_29 AC 102 ms
76,928 KB
testcase_30 AC 90 ms
77,056 KB
testcase_31 AC 215 ms
77,360 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys, random
input = lambda : sys.stdin.readline().rstrip()


write = lambda x: sys.stdout.write(x+"\n"); writef = lambda x: print("{:.12f}".format(x))
debug = lambda x: sys.stderr.write(x+"\n")
YES="Yes"; NO="No"; pans = lambda v: print(YES if v else NO); INF=10**18
LI = lambda : list(map(int, input().split())); II=lambda : int(input())
def debug(_l_):
    for s in _l_.split():
        print(f"{s}={eval(s)}", end=" ")
    print()
def dlist(*l, fill=0):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [dlist(*ll, fill=fill) for _ in range(l[0])]

def floor_sum_unsighned(n,m,a,b):
    """sum(((a*i+b)//m) for i in range(n))
    n>=0, m>=1
    """
    ans = 0
    if a>=m:
        ans += (n-1)*n*(a//m)//2
        a %= m
    if b>=m:
        ans += n*(b//m)
        b %= m
    y_max = (a*n + b) // m
    x_max = y_max*m - b
    if y_max==0:
        return ans
    ans += (n - (x_max+a-1)//a) * y_max
    ans += floor_sum(y_max, a, m, (a - x_max%a)%a)
    return ans

# assert(0 <= n && n < (1LL << 32));
#     assert(1 <= m && m < (1LL << 32));
#     unsigned long long ans = 0;
#     if (a < 0) {
#         unsigned long long a2 = internal::safe_mod(a, m);
#         ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m);
#         a = a2;
#     }
#     if (b < 0) {
#         unsigned long long b2 = internal::safe_mod(b, m);
#         ans -= 1ULL * n * ((b2 - b) / m);
#         b = b2;
#     }
#     return ans + internal::floor_sum_unsigned(n, m, a, b);
# }

def floor_sum(n,m,a,b):
    assert(0<=n and 1<=m)
    ans = 0
    if a<0:
        a2 = a%m
        ans -= n*(n-1)//2 * ((a2-a)//m)
        a = a2
    if b<0:
        b2 = b%m
        ans -= n * ((b2-b)//m)
        b = b2
    return ans + floor_sum_unsighned(n,m,a,b)

import math
t = II()
for _ in range(t):
    p,q,k = LI()
    g = math.gcd(p,q)
#     print(p,q,g)
    p //= g
    q //= g
    ok = 10**18 + 100
    ng = 0
    while abs(ok-ng)>1:
        mm = (ok+ng)//2
        qq = min(mm//p + 1, q)
#         qq = q
        val = floor_sum(qq, q, -p, mm) + qq
        if val>k:
            ok = mm
        else:
            ng = mm
    ans = ok * g
    print(ans)
0