結果

問題 No.1899 L1 Cafe
ユーザー taiga0629kyoprotaiga0629kyopro
提出日時 2022-04-08 22:56:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 423 ms / 2,000 ms
コード長 700 bytes
コンパイル時間 1,007 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 77,856 KB
最終ジャッジ日時 2024-05-06 08:37:53
合計ジャッジ時間 6,472 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
52,276 KB
testcase_01 AC 409 ms
77,056 KB
testcase_02 AC 401 ms
77,076 KB
testcase_03 AC 288 ms
76,816 KB
testcase_04 AC 314 ms
76,672 KB
testcase_05 AC 215 ms
76,544 KB
testcase_06 AC 410 ms
77,284 KB
testcase_07 AC 370 ms
76,844 KB
testcase_08 AC 362 ms
76,972 KB
testcase_09 AC 320 ms
77,176 KB
testcase_10 AC 385 ms
76,416 KB
testcase_11 AC 359 ms
77,856 KB
testcase_12 AC 423 ms
77,244 KB
権限があれば一括ダウンロードができます

ソースコード

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