結果

問題 No.1899 L1 Cafe
ユーザー taiga0629kyoprotaiga0629kyopro
提出日時 2022-04-08 22:56:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 444 ms / 2,000 ms
コード長 700 bytes
コンパイル時間 431 ms
コンパイル使用メモリ 87,200 KB
実行使用メモリ 80,396 KB
最終ジャッジ日時 2023-08-19 01:28:23
合計ジャッジ時間 6,295 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
71,380 KB
testcase_01 AC 444 ms
79,904 KB
testcase_02 AC 363 ms
78,488 KB
testcase_03 AC 269 ms
78,340 KB
testcase_04 AC 314 ms
78,492 KB
testcase_05 AC 215 ms
78,396 KB
testcase_06 AC 392 ms
78,544 KB
testcase_07 AC 353 ms
78,852 KB
testcase_08 AC 350 ms
78,908 KB
testcase_09 AC 322 ms
79,360 KB
testcase_10 AC 384 ms
78,756 KB
testcase_11 AC 359 ms
79,248 KB
testcase_12 AC 420 ms
80,396 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