結果

問題 No.1899 L1 Cafe
ユーザー taiga0629kyoprotaiga0629kyopro
提出日時 2022-04-08 22:56:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 456 ms / 2,000 ms
コード長 700 bytes
コンパイル時間 652 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 77,592 KB
最終ジャッジ日時 2024-11-28 13:53:49
合計ジャッジ時間 6,195 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 


def floor_sum(n,m,a,b):
    #Σ i=0→(n-1) [(a*i+b)/m]をO(loga+logm)で求める 1<=n,m  a,bはall
    if not(0<=a<m and 0<=b<m):
        k=(a-a%m)//m
        l=(b-b%m)//m
        return floor_sum(n,m,a%m,b%m)+(l)*n+(k)*n*(n-1)//2

    if a==0:
        return (b//m)*n
    if n==1:
        return b//m
    if a>=m or b>=m:
        return floor_sum(n,m,a%m,b%m)+(b//m)*n+(a//m)*n*(n-1)//2
    y=(a*n+b)//m
    z=(a*n+b)%m
    return floor_sum(y,a,m,z)






T=int(input())
for _ in range(T):
    n,a,b=map(int,input().split())
    cnt=n//a
    ansa=(cnt)*(n-a-a*cnt+n)//2
    cnt=n//b
    ansb=(cnt)*(n-b-b*cnt+n)//2
    ansab=floor_sum(n//a+1,b,-a,n)-n//b
    ans=ansa+ansb-ansab

    print(ans)
0