結果
問題 |
No.752 mod数列
|
ユーザー |
|
提出日時 | 2024-07-05 21:58:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 988 ms / 2,000 ms |
コード長 | 731 bytes |
コンパイル時間 | 167 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 99,584 KB |
最終ジャッジ日時 | 2024-07-05 21:59:02 |
合計ジャッジ時間 | 10,182 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
from sys import stdin def input(): return stdin.readline()[:-1] B = int(1e6) p, q = map(int, input().split()) rem = [0] + [p%i for i in range(1, B+1)] for i in range(1, B + 1): rem[i] += rem[i - 1] quo = [0] * (B + 1) for i in range(B + 1): quo[i] = (p//(i + 1)) + 1 for _ in range(q): l, r = map(int, input().split()) res = rem[min(r, B)] - rem[min(l - 1, B)] l = max(l, B + 1) if l <= r: s, e = p//l, p//r for t in range(s, e, -1): right = quo[t - 1] - 1 res += p * (right - l + 1) res -= (t * (right - l + 1) * (right + l)) // 2 l = quo[t - 1] res += p * (r - l + 1) res -= (e * (r - l + 1) * (l + r)) // 2 print(res)