結果

問題 No.2066 Simple Math !
コンテスト
ユーザー 👑 Kazun
提出日時 2022-09-02 22:51:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,020 bytes
コンパイル時間 458 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 161,228 KB
最終ジャッジ日時 2024-11-16 05:22:14
合計ジャッジ時間 60,220 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 16 TLE * 15
権限があれば一括ダウンロードができます

ソースコード

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