結果
問題 |
No.752 mod数列
|
ユーザー |
|
提出日時 | 2025-09-24 00:27:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 282 ms / 2,000 ms |
コード長 | 1,204 bytes |
コンパイル時間 | 1,644 ms |
コンパイル使用メモリ | 194,736 KB |
実行使用メモリ | 23,172 KB |
最終ジャッジ日時 | 2025-09-24 00:27:31 |
合計ジャッジ時間 | 7,099 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long int p,q,l,r; long long int a[1000001]; long long int psum[1000001]; int arr[1000001]; int main(void) { cin.tie(0); ios::sync_with_stdio(false); cin >> p >> q; arr[0] = p + 1; for(int i=1;i<=1000000;i++) { a[i] = p%i; psum[i] = psum[i-1] + a[i]; arr[i] = p/(i+1) + 1; } while(q--) { cin >> l >> r; if(r<=1000000) { cout << psum[r] - psum[l-1] << '\n'; } else { long long int res = 0; if(l<=1000000) { res += psum[1000000]; res -= psum[l-1]; l = 1000001; } long long int x = p/l; long long int y = p/r; while(x>y) { long long int v = arr[x-1]-1; long long int val = p*(v-l+1); val -= (x*(v+l)*(v-l+1)/2); res += val; x--; l = arr[x]; } res += (p*(r-l+1)); res -= (y*(r+l)*(r-l+1)/2); cout << res << '\n'; } } return 0; }