結果
問題 | No.2066 Simple Math ! |
ユーザー |
![]() |
提出日時 | 2022-08-02 16:10:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,066 ms / 2,000 ms |
コード長 | 1,009 bytes |
コンパイル時間 | 307 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 78,964 KB |
最終ジャッジ日時 | 2024-11-15 19:08:03 |
合計ジャッジ時間 | 23,538 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
def floor_sum(n,m,a,b):ans=0while True:if a>=m:ans+=(n-1)*n*(a//m)//2a%=mif b>=m:ans+=n*(b//m)b%=my_max=(a*n+b)//mx_max=(y_max*m-b)if y_max==0:return ansans+=(n-(x_max+a-1)//a)*y_maxn,m,a,b=y_max,a,m,(a-x_max%a)%adef calc1(p,q,n):x=(q*n)//preturn (x+1)*n-floor_sum(x+1,q,p,0)def calc2(p,q,n,m):ng,ok=q,0while abs(ok-ng)>1:mid=(ok+ng)//2if floor_sum(n,q,p,q-mid)-floor_sum(n,q,p,0)>=n+1-m:ok=midelse:ng=midreturn okimport mathdef solve(p,q,k):g=math.gcd(p,q)p,q=min(p,q)//g,max(p,q)//gm=q*(p-1)-(p-1)*(q-1)//2if k>m:res=k-m-1+q*(p-1)return res*gng,ok=0,p+1while abs(ok-ng)>1:mid=(ok+ng)//2if k<=calc1(p,q,mid):ok=midelse:ng=midif ok==0:x=kelse:x=k-calc1(p,q,ok-1)return (q*(ok-1)+calc2(p,q,(ok*q)//p+1,x))*gt=int(input())for _ in range(t):p,q,k=map(int,input().split())print(solve(p,q,k+1))