結果

問題 No.3101 Range Eratosthenes Query
コンテスト
ユーザー startcpp
提出日時 2025-04-12 03:46:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 959 ms / 3,000 ms
コード長 1,183 bytes
コンパイル時間 1,216 ms
コンパイル使用メモリ 84,068 KB
実行使用メモリ 106,928 KB
最終ジャッジ日時 2025-04-12 03:46:29
合計ジャッジ時間 23,618 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <atcoder/fenwicktree>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
using namespace atcoder;
typedef tuple<int, int, int> T;

const int MAX = 1000001;
bool isPrime[MAX];
vector<int> ps[MAX];
int q;
vector<T> vecT;
vector<int> nums[MAX]; //nums[最大の約数]

int main() {
	int i, j;

	rep(i, MAX) isPrime[i] = true;
	isPrime[0] = isPrime[1] = false;
	for (i = 2; i < MAX; i++) {
		if (isPrime[i]) {
			for (j = 2 * i; j < MAX; j += i) {
				isPrime[j] = false;
				ps[j].push_back(i);
			}
			ps[i].push_back(i);
		}
	}
	
	cin >> q;
	rep(i, q) {
		int l, r; cin >> l >> r;
		vecT.push_back(T(l, r, i));
	}
	sort(vecT.begin(), vecT.end());

	for (i = 1; i < MAX; i++) {
		int y = (i == 1) ? 0 : i / ps[i][0];
		nums[y].push_back(i);
	}

	vector<int> ans(q, -1);
	fenwick_tree<int> fw(MAX);
	int cor = 0;
	rep(i, vecT.size()) {
		int l = get<0>(vecT[i]), r = get<1>(vecT[i]), id = get<2>(vecT[i]);
		for (; cor < l; cor++) {
			for (int num: nums[cor]) {
				fw.add(num, 1);
			}
		}
		ans[id] = fw.sum(l, r + 1);
	}

	rep(i, ans.size()) {
		cout << ans[i] << endl;
	}
	return 0;
}
0