結果

問題 No.1918 Simple Math ?
コンテスト
ユーザー LyricalMaestro
提出日時 2024-09-09 01:53:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,329 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 82,144 KB
最終ジャッジ日時 2024-09-09 01:53:22
合計ジャッジ時間 9,792 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1918

MOD = 10 ** 9 + 7

def solve(a, N):
    
    n1 = ((a + 1) // 2) + 1
    answer = 0
    low = 1
    for i in range(1, min(n1, N) + 1):
        x = a * i
        high = 10 ** 9
        while high - low > 1:
            mid = (high + low) // 2
            if mid ** 2 <= x:
                low = mid
            else:
                high = mid
        if high ** 2 <= x:
            v = high
        else:
            v = low
        
        answer += v
        answer %= MOD
        low = v
    
    # 最上位から
    low = 0
    high = 10 ** 9
    while high - low > 1:
        mid = (high + low) // 2
        if mid ** 2 <= a * N:
            low = mid
        else:
            high = mid
    if high ** 2 <= a * N:
        v = high
    else:
        v = low

    n0 = N
    while n1 < n0:
        x = (v ** 2) // a
        if x * a < v ** 2:
            x += 1
        x = max(n1 + 1, x)

        y = (n0 - x + 1) % MOD
        answer += (y * v) % MOD
        answer %= MOD
        v -= 1
        n0 = x - 1
    return answer


def main():
    T = int(input())
    answers = []
    for _ in range(T):
        a, N = map(int, input().split())
        ans = solve(a, N)
        answers.append(ans)

    for ans in answers:
        print(ans)

if __name__ == "__main__":
    main()
0