結果

問題 No.752 mod数列
ユーザー betrue12
提出日時 2018-11-09 22:25:05
言語 C++17(1z)
(gcc 9.2.0)
結果
AC  
実行時間 308 ms
コード長 1,286 Byte
コンパイル時間 1,844 ms
使用メモリ 3,988 KB
最終ジャッジ日時 2020-01-01 04:28:58

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0.txt AC 0 ms
3,312 KB
1.txt AC 0 ms
3,288 KB
2.txt AC 4 ms
3,308 KB
3.txt AC 0 ms
3,156 KB
4.txt AC 0 ms
3,216 KB
5.txt AC 4 ms
3,292 KB
6.txt AC 0 ms
3,164 KB
7.txt AC 0 ms
3,176 KB
8.txt AC 4 ms
3,152 KB
9.txt AC 4 ms
3,148 KB
10.txt AC 4 ms
3,740 KB
11.txt AC 4 ms
3,408 KB
12.txt AC 8 ms
3,600 KB
13.txt AC 4 ms
3,540 KB
14.txt AC 4 ms
3,752 KB
15.txt AC 236 ms
3,224 KB
16.txt AC 260 ms
3,804 KB
17.txt AC 284 ms
3,988 KB
18.txt AC 252 ms
3,296 KB
19.txt AC 272 ms
3,208 KB
20.txt AC 288 ms
3,356 KB
21.txt AC 280 ms
3,324 KB
22.txt AC 280 ms
3,192 KB
23.txt AC 300 ms
3,236 KB
24.txt AC 304 ms
3,176 KB
25.txt AC 88 ms
3,828 KB
26.txt AC 224 ms
3,856 KB
27.txt AC 164 ms
3,804 KB
28.txt AC 204 ms
3,828 KB
29.txt AC 276 ms
3,604 KB
30.txt AC 308 ms
3,704 KB
sample1.txt AC 0 ms
3,212 KB
sample2.txt AC 4 ms
3,148 KB
sample3.txt AC 0 ms
3,648 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;

int64_t r[100001], s[100001], mn[100001];

int main(){
    int64_t P;
    int Q;
    cin >> P >> Q;

    int64_t bound = 1;
    while(bound*bound <= P) bound++;

    r[0] = 0;
    for(int i=1; i<bound; i++){
        r[i] = r[i-1] + P%i;
    }

    s[0] = 0;
    for(int i=0; i<=P/bound; i++){
        mn[i] = P/(i+1) + 1;
        if(i>0){
            int64_t num = mn[i-1] - mn[i];
            s[i] = s[i-1] + P*num - (mn[i-1]-1 + mn[i]) * num / 2 * i;
        }
    }

    while(Q--){
        int64_t Lo, Ro;
        cin >> Lo >> Ro;
        int64_t ans = 0;
        if(Lo <= bound-1){
            int L = Lo, R = min(bound-1, Ro);
            ans += r[R] - r[L-1];
        }
        if(bound <= Ro){
            int L = max(Lo, bound), R = Ro;
            int lq = P/L, rq = P/R;
            if(lq == rq){
                int64_t num = R - L + 1;
                ans += P*num - (R+L) * num / 2 * lq;
            }else{
                ans += s[lq-1] - s[rq];
                int64_t num = R - mn[rq] + 1;
                ans += P*num - (R+mn[rq]) * num / 2 * rq;
                num = mn[lq-1] - L;
                ans += P*num - (mn[lq-1]-1+L) * num / 2 * lq;
            }
        }
        cout << ans << endl;
    }


    return 0;
}
0