結果

問題 No.3079 アルベド
ユーザー nonamaenonamae
提出日時 2022-07-12 12:35:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,162 ms / 2,000 ms
コード長 1,021 bytes
コンパイル時間 2,558 ms
コンパイル使用メモリ 201,820 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-05 12:38:42
合計ジャッジ時間 8,786 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 165 ms
4,376 KB
testcase_01 AC 1,162 ms
4,376 KB
testcase_02 AC 715 ms
4,376 KB
testcase_03 AC 486 ms
4,380 KB
testcase_04 AC 898 ms
4,376 KB
testcase_05 AC 657 ms
4,380 KB
testcase_06 AC 821 ms
4,380 KB
testcase_07 AC 140 ms
4,376 KB
testcase_08 AC 214 ms
4,376 KB
testcase_09 AC 623 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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