結果

問題 No.2066 Simple Math !
ユーザー 👑 KazunKazun
提出日時 2022-09-02 22:51:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,020 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 86,652 KB
最終ジャッジ日時 2024-04-27 22:30:39
合計ジャッジ時間 4,404 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
57,600 KB
testcase_01 AC 86 ms
76,416 KB
testcase_02 AC 223 ms
77,256 KB
testcase_03 AC 71 ms
76,132 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def floor_sum(A,B,M,N):
    """sum_{i=0}^{N-1} floor((A*i+B)/M) を求める.
    """
    T=0
    while True:
        T+=((N-1)*N//2)*(A//M)
        A%=M

        T+=N*(B//M)
        B%=M

        y=(A*N+B)//M
        x=B-y*M

        if y==0:
            return T

        T+=(N+x//A)*y
        A,B,M,N=M,x%A,A,y

def Floor_Sum(A:int,B:int,M:int,N:int,K=0):
    """sum_{i=K}^N floor((A*i+B)/M) を求める.
    """

    if K==0:
        return floor_sum(A,B,M,N+1)
    else:
        return floor_sum(A,B,M,N+1)-floor_sum(A,B,M,K)

def Extend_Euclid(a:int,b:int):
    """gcd(a,b) と ax+by=gcd(a,b) を満たす整数 x,y の例を挙げる.

    [Input]
    a,b: 整数

    [Output]
    (x,y,gcd(a,b))
    """
    s,t,u,v=1,0,0,1
    while b:
        q,a,b=a//b,b,a%b
        s,t=t,s-q*t
        u,v=v,u-q*v
    return s,u,a

def General_Binary_Increase_Search_Integer(L, R, cond, default=None):
    """ 条件式が単調増加であるとき, 整数上で二部探索を行う.

    L: 解の下限
    R: 解の上限
    cond: 条件(1変数関数, 広義単調増加を満たす)
    default: Lで条件を満たさないときの返り値
    """

    if not(cond(R)):
        return default

    if cond(L):
        return L

    R+=1
    while R-L>1:
        C=L+(R-L)//2
        if cond(C):
            R=C
        else:
            L=C
    return R
#==================================================
def solve(P,Q,K):
    a,b,g=Extend_Euclid(P,Q)
    if g>=2:
        return g*solve(P//g, Q//g, K)

    if P==1 or Q==1:
        return K

    def calc(n):
        X=Floor_Sum(b,0,P,n,1)
        Y=Floor_Sum(-a,-1,Q,n,0)
        return X-Y

    L=calc((P-1)*(Q-1))
    if L>K:
        return General_Binary_Increase_Search_Integer(0,(P-1)*(Q-1), lambda n:calc(n)>K)
    else:
        return (P-1)*(Q-1)+(K-L)+1

import sys
input=sys.stdin.readline
write=sys.stdout.write

T=int(input())

Ans=[0]*T
for t in range(T):
    P,Q,K=map(int,input().split())
    Ans[t]=solve(P,Q,K)

write("\n".join(map(str,Ans)))
0