結果

問題 No.752 mod数列
ユーザー ats5515
提出日時 2018-11-09 22:28:50
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 420 ms
コード長 878 Byte
コンパイル時間 540 ms
使用メモリ 22,240 KB
最終ジャッジ日時 2020-01-01 04:30:47

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0.txt AC 0 ms
3,544 KB
1.txt AC 4 ms
3,552 KB
2.txt AC 0 ms
3,460 KB
3.txt AC 0 ms
3,500 KB
4.txt AC 4 ms
3,324 KB
5.txt AC 0 ms
3,668 KB
6.txt AC 4 ms
3,468 KB
7.txt AC 4 ms
3,604 KB
8.txt AC 4 ms
3,620 KB
9.txt AC 4 ms
3,532 KB
10.txt AC 28 ms
9,728 KB
11.txt AC 16 ms
6,200 KB
12.txt AC 20 ms
8,524 KB
13.txt AC 16 ms
7,504 KB
14.txt AC 28 ms
9,820 KB
15.txt AC 212 ms
4,436 KB
16.txt AC 280 ms
7,512 KB
17.txt AC 408 ms
19,644 KB
18.txt AC 292 ms
9,540 KB
19.txt AC 312 ms
11,444 KB
20.txt AC 396 ms
17,468 KB
21.txt AC 408 ms
17,468 KB
22.txt AC 400 ms
16,848 KB
23.txt AC 412 ms
17,988 KB
24.txt AC 400 ms
17,492 KB
25.txt AC 136 ms
14,740 KB
26.txt AC 348 ms
18,996 KB
27.txt AC 232 ms
15,372 KB
28.txt AC 312 ms
18,280 KB
29.txt AC 356 ms
15,464 KB
30.txt AC 420 ms
22,240 KB
sample1.txt AC 4 ms
3,260 KB
sample2.txt AC 0 ms
3,388 KB
sample3.txt AC 24 ms
8,248 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <assert.h>
using namespace std;
#define int long long
int MOD = 1000000007;
map<int, int> dp;
int P, Q;
int solve(int a) {
	if (dp.count(a) != 0) {
		return dp[a];
	}
	//cerr << a << endl;
	int m = P / a;
	int x = (P / (m + 1)) + 1;
	assert((P / a) == (P / x));
	if (x != 1)	assert((P / x) != (P / (x - 1)));
	int a1 = P%a;
	int a2 = P%x;
	return dp[a] = ((((a1 + a2) * (a - x + 1)) / 2) + solve(x - 1));
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	dp[0] = 0;
	cin >> P >> Q;
	vector<int> L(Q);
	vector<int> R(Q);
	for (int i = 0; i < Q; i++) {
		cin >> L[i] >> R[i];
	}
	for (int i = 0; i < Q; i++) {
		int res = solve(R[i]) - solve(L[i] - 1);
		cout << res << endl;
	}
}
0