提出 #64527159

---

ソースコード 拡げる

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;

const int MAXQ = 200000;
const int MAXVAL = 1000001;

struct Query
{
	int index;
	ll x, ans;
};

int q;
Query qs[MAXQ+2];
int lp[MAXVAL+2], lpjump[MAXVAL+2];
vector<int> primes;

void calcCiur()
{
	lpjump[1] = 1;
	for (int i = 2; i <= MAXVAL; i++) {
		if (!lp[i]) {
			lp[i] = i;
			lpjump[i] = 1;
			primes.push_back(i);
		}
		for (int j = 0; i * primes[j] <= MAXVAL; j++) {
			lp[i * primes[j]] = primes[j];
			if (primes[j] == lp[i]) {
				lpjump[i * primes[j]] = lpjump[i];
				break;
			}
			lpjump[i * primes[j]] = i;
		}
	}
}

bool isValid(ll x)
{
	return (lpjump[x] != 1 && lpjump[lpjump[x]] == 1);
}

int main()
{
	calcCiur();
	cin >> q;
	for (int i = 1; i <= q; i++) {
		qs[i].index = i;
		cin >> qs[i].x;
	}
	sort(qs+1, qs+q+1, [&](const Query &a, const Query &b) { return a.x < b.x; });
	long long x = 6;
	for (int i = 1; i <= q; i++) {
		qs[i].ans = qs[i-1].ans;
		while (x * x <= qs[i].x) {
			if (isValid(x)) qs[i].ans = x * x;
			x++;
		}
	}
	sort(qs+1, qs+q+1, [&](const Query &a, const Query &b) { return a.index < b.index; });
	for (int i = 1; i <= q; i++) {
		cout << qs[i].ans << '\n';
	}
	return 0;
}

提出情報

ジャッジ結果