Codeforces #643 Div2 F. Guess Divisors Count

あけましておめでとうございます。
https://codeforces.com/contest/1355/problem/F

問題

1～10^9の範囲の謎の正整数Xがあるので、このXの約数の数を当てたい。
真の解に対し、差が7以下か、比が倍半分の間ならよい。

このため、整数Q(10^18以下)を指定するとGCD(X,Q)を返すクエリを22回まで利用できる。

解法

まず、Xを素因数分解したときにおよそ800以上の素因数は無視してよい。
800^3＞10^9/2なので、800以上の素因数は高々2個しか含まれず、これによる解への寄与は4倍分である。
元々倍半分の誤差は許容されるので、800未満の素因数による約数の数の倍を答えておけば、合わせてこの4倍を吸収できる。

あとは800未満の素因数を考える。
まずは、800以下の素数を10^18以下の範囲で掛け合わせていくつかのQにまとめ、Xの素因数を求めよう。

次に、各素因数について素因数の何乗分がXに寄与するかを求める。
最後に、上で書いた通り2倍した値を回答しておけばよい。

int T;
vector<int> P={
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,
181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797};


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll V[30]={};
	
	int cur=0;
	for(x=0;x<P.size();x++) {
		ll v=1;
		while(x<P.size()&&1.0*v*P[x]<=1e18) {
			v*=P[x];
			x++;
		}
		V[cur++]=v;
	}
	cin>>T;
	while(T--) {
		ll R[30]={};
		FOR(i,cur) {
			cout<<"? "<<V[i]<<endl;
			cin>>R[i];
		}
		
		vector<int> cand;
		FORR(p,P) {
			FOR(i,cur) if(R[i]%p==0) cand.push_back(p);
		}
		if(cand.size()%2==1) cand.push_back(1);
		
		
		ll X=0;
		ll D=1;
		for(x=0;x<cand.size();x+=2) {
			ll p[2]={1,1};
			while(p[0]*cand[x]<1000000000) p[0]*=cand[x];
			while(cand[x+1]>1 && p[1]*cand[x+1]<1000000000) p[1]*=cand[x+1];
			
			cout<<"? "<<p[0]*p[1]<<endl;
			ll v;
			cin>>v;
			int num=1;
			while(v%cand[x]==0) num++, v/=cand[x];
			D*=num;
			num=1;
			while(cand[x+1]>1 && v%cand[x+1]==0) num++, v/=cand[x+1];
			D*=num;
		}
		cout<<"! "<<D*2<<endl;
	}
}

まとめ

解法はともかく、誤差の設定が非常に特徴的な問題。