#795200 (PyPy3) No.2066 Simple Math !

• 問題: No.2066 Simple Math !
• ユーザー: shotoyoo
• 提出日時: 2022-09-03 13:41:11
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,268 ms / 2,000 ms
• コード長: 2,156 bytes
• コンパイル時間: 659 ms
• コンパイル使用メモリ: 82,304 KB
• 実行使用メモリ: 81,584 KB
• 最終ジャッジ日時: 2024-11-17 03:33:52
• 合計ジャッジ時間: 27,053 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 1
other	AC * 31

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX