[PS]BOJ 1016平方ㄴ数

5801 ワード
ps テキストリンク
https://www.acmicpc.net/problem/1016
これはエラストネスの体の問題です.
平方ㄴ数を計算するのに時間がかかるので、平方ㅇ数を求めて、残りを数えるのは簡単です.
sqrt(max)以下の数字の平方の倍数をチェックすればいいのです.
エラスドテネスのふるいを使用する場合、ゼロから開始しなければならないことに注意してください.
min値を減算すると、0から1000000以内に計算できます.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using lld = long long;
int main() {
	const int N = 1000001;
	lld minv, maxv;
	cin >> minv >> maxv;
	vector<bool> bloom(N, false);
	for (lld i = 2; i*i <= maxv; i++) {
		lld k = minv / (i*i);
		if (k*i*i != minv)k++;
		if (k*i*i > maxv && bloom[k*i*i - minv])continue;
		while (k*i*i <= maxv) {
			bloom[k*i*i - minv] = true;
			k++;
		}
	}
	int A=std::count(bloom.begin(), bloom.begin()+(maxv-minv+1), false);
	cout << A << endl;
	return 0;
}
[解決] "処理により警告を処理します.
Linuxに関する知識