Codeforces ECR #120 : F. Quadratic Set

これ系いつも忘れる。
https://codeforces.com/contest/1622/problem/F

問題

正整数Nが与えられる。
整数1～Nの部分集合Sのうち、以下を満たす最大要素数のものを1つ構築せよ。

• 各要素aに対し、a!を掛け合わせたものが平方数である。

解法

• Nが偶数の場合、Sは1～Nから2とN/2を除いたものが解になるので、(N-2)要素以上のSを構築できる。
• Nが偶数の場合、Sは1～Nから2と(N-1)/2とNを除いたものが解になるので、(N-3)要素以上のSを構築できる。

よって、必ず(N-3)要素以上のSを構築できる。
あとは(N-1)、(N-2)、N要素のSが構築可能か判定しよう。

素数に異なる乱数を割り当てることで、
F(a) := aを素因数分解したときの各素数に対応する乱数のxor
G(a) := F(1)～F(a)のxor
とすると、a!に対応するハッシュ値をG(a)で表現できる。

あとは
H = G(1) xor G(2) xor ... xor G(N)
とすると、

• H=0なら、Sは{1,2,...,N}
• H≠0かつG(x) = Hとなるxがあれば、Sは{1,2,...,N}-{x}
• H≠0かつG(x) xor G(y) = Hとなるx,yがあれば、Sは{1,2,...,N}-{x,y}

となるので、これらを総当たりしよう。

const int prime_max = 1100001;
vector<int> prime;
int NP,divp[prime_max];
ll chash[prime_max];
ll FS[prime_max];
unordered_map<ll,int> rev;
int N;

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

std::random_device rnd;     // 非決定的な乱数生成器
std::mt19937 mt(rnd());            // メルセンヌ・ツイスタの32ビット版、引数は初期シード

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cprime();

	ll th=0;
	for(i=2;i<=N;i++) {
		chash[i]=((1LL*mt())<<31)+mt()+i;
		FS[i]=FS[i-1];
		x=i;
		while(x>1) {
			FS[i]^=chash[divp[x]];
			x/=divp[x];
		}
		th^=FS[i];
		rev[FS[i]]=i;
	}
	
	vector<int> exc;
	
	if(th==0) {
		exc={};
	}
	else if(rev.count(th)) {
		exc={rev[th]};
	}
	else {
		rev.clear();
		for(i=2;i<=N;i++) {
			ll tmp=th^FS[i];
			if(rev.count(tmp)) {
				exc={rev[tmp],i};
			}
			rev[FS[i]]=i;
		}
		if(exc.empty()) {
			exc={2,N,N/2};
		}
	}
	
	cout<<N-(exc.size())<<endl;
	ll tc=0;
	for(i=1;i<=N;i++) {
		if(count(ALL(exc),i)==0) {
			cout<<i<<" ";
			tc^=FS[i];
		}
	}
	cout<<endl;
}

まとめ

アイデアだけ聞くと難しくないんだよな…。