結果

問題 No.1918 Simple Math ?
ユーザー tamatotamato
提出日時 2022-04-29 23:44:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 904 bytes
コンパイル時間 136 ms
コンパイル使用メモリ 82,044 KB
実行使用メモリ 83,640 KB
最終ジャッジ日時 2024-06-29 05:31:10
合計ジャッジ時間 4,199 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 1000000007


def main():
    import sys
    from math import floor, sqrt
    input = sys.stdin.readline

    def floor_sqrt(a):
        x0 = floor(sqrt(a))
        res = 0
        for x in range(x0 - 3, x0 + 4):
            if x <= 0:
                continue
            if x ** 2 <= a:
                res = max(res, x)
        return res

    for _ in range(int(input())):
        a, N = map(int, input().split())
        ans = prev = floor_sqrt(a)
        n = 1
        while n < N:
            n_new = ((prev + 1) ** 2 - 1) // a + 1
            val = floor_sqrt(a * n_new)
            assert val ** 2 <= a * n_new < (val + 1) ** 2
            if n_new <= N:
                ans += val + (n_new - n - 1) * prev
            else:
                ans += prev * (N - n)
            ans %= mod
            n = n_new
            prev = val
        print(ans)


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