結果

問題 No.8079 アルベド
コンテスト
ユーザー nonamae
提出日時 2022-07-12 12:35:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,127 ms / 2,000 ms
コード長 1,021 bytes
コンパイル時間 2,070 ms
コンパイル使用メモリ 197,356 KB
最終ジャッジ日時 2025-01-30 06:42:55
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using u64 = uint_fast64_t;

u64 count_primes(const u64 n) {
	auto v = (unsigned int)sqrt(n);
	vector<u64>			 higher(v + 2, 0);
	vector<unsigned int> lower(v + 2, 0);
	vector<bool>		 used(v + 2, false);
	u64 result = n - 1;
	for (unsigned int p = 2; p <= v; p++) {
		lower[p] = p - 1;
		higher[p] = n / p - 1;
	}
	for (unsigned int p = 2; p <= v; p++) {
		if (lower[p] == lower[p - 1]) continue;
		auto temp = lower[p - 1];
		result -= higher[p] - temp;
		auto pxp = (u64) p * p;
		auto end = min<u64>(v, n / pxp);
		auto j = 1 + (p & 1);
		for (auto i = p + j; i <= end + 1; i += j) {
			if (used[i]) continue;
			auto d = i * p;
			if (d <= v) higher[i] -= higher[d] - temp;
			else 		higher[i] -= lower[n / d] - temp;
		}
		for (auto i = v; i >= pxp; i--) lower[i] -= lower[i / p] - temp;
		for (auto i = pxp; i <= end; i += p * j) used[i] = true;
	}
	return result;
}


int main() {
	u64 a, b;
	cin >> a;
	while (a--) {
		cin >> b;
		cout << count_primes(b) << '\n';
	}
}
0