Codeforces #1011 : Div2 E. Serval and Modulo

なるほど。
https://codeforces.com/contest/2085/problem/E

問題

整数列Aが与えられる。
秘密の整数Kがあるとして、AからBを以下のように作る。
B[i]=A[i] % Kとしたのち、Bをシャッフルする。

Kが存在するか判定し、存在するなら1つ答えよ。

解法

• sum(A)＜sum(B)なら解なし。
• sum(A)=sum(B)の場合、Aを並び替えてBとなるか判定すること。
• sum(A)＞sum(B)の場合、sum(A)=sum(B) + nKのはずである。
  • よってKはsum(A)-sum(B)の約数でなければならないので、それらを総当たりしよう。

int T,N,A[10101],B[10101];
int C[10101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll sum=0;
		FOR(i,N) {
			cin>>A[i];
			sum+=A[i];
		}
		FOR(i,N) {
			cin>>B[i];
			sum-=B[i];
		}
		sort(A,A+N);
		sort(B,B+N);
		if(sum<0) {
			cout<<-1<<endl;
			continue;
		}
		else if(sum==0) {
			FOR(i,N) if(A[i]!=B[i]) break;
			if(i==N) {
				cout<<100000000<<endl;
			}
			else {
				cout<<-1<<endl;
			}
		}
		else {
			vector<ll> cand;
			for(ll a=1;a*a<=sum;a++) if(sum%a==0) {
				cand.push_back(a);
				cand.push_back(sum/a);
			}
			ll ret=-1;
			FORR(a,cand) if(a<=A[N-1]) {
				FOR(i,N) C[i]=A[i]%a;
				sort(C,C+N);
				FOR(i,N) if(B[i]!=C[i]) break;
				if(i==N) ret=a;
			}
			cout<<ret<<endl;
		}
		
	}
}

まとめ

これ思いつかなかった…。