結果
| 問題 |
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;
}