Codeforces #289 Div2 D. Restoring Numbers

ちょっと考える問題。
http://codeforces.com/contest/509/problem/D

問題

２つの数列A[i],B[j]と整数Kから行列V[i][j]を作る。
V[i][j]はV[i][j] = (A[i] + B[j]) % Kにより生成される。

ここでV[i][j]が与えられたとき、それを生成するようなA[i],B[j],Kが存在するか。
存在するなら１例を示せ。

解法

V[i][j]の最小値をV[x][y]とする。
この際A[x]=V[x][y]、B[y]=0と仮置きする。

後はA[x]とB[y]が求まれば、V[i][j]から他のA[i]、B[j]が求まる。
また、A[i]+B[j]!=V[i][j]の時、Kの候補をA[i]+B[j]-V[i][j]とする。

Kの候補に対して再度(A[i]+B[j])%K=V[i][j]を検証し、不一致なら解なしとなる。

int R,C;
ll W[105][105];
ll my=0,mx=0;
ll A[105],B[105];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>R>>C;
	FOR(y,R) FOR(x,C) {
		cin>>W[y][x];
		if(W[y][x]<W[my][mx]) my=y,mx=x;
	}
	
	ll mo=1LL<<40;
	
	A[my]=W[my][mx];
	FOR(x,C) B[x]=W[my][x]-A[my];
	FOR(y,R) A[y]=W[y][0]-B[0];
	FOR(y,R) FOR(x,C) if(W[y][x]!=(A[y]+B[x])) mo=abs(A[y]+B[x]-W[y][x]);
	FOR(y,R) A[y]=(A[y]%mo+mo)%mo;
	FOR(x,C) B[x]=(B[x]%mo+mo)%mo;
	FOR(y,R) FOR(x,C) if(W[y][x]!=(A[y]+B[x])%mo) return _P("NO\n");
	_P("YES\n");
	_P("%I64d\n",mo);
	FOR(y,R) _P("%s%I64d",(y?" ":""),A[y]);
	_P("\n");
	FOR(x,C) _P("%s%I64d",(x?" ":""),B[x]);
	_P("\n");
	
}

まとめ

本番は先に面倒な処理でKを求めてしまった。
それは置いておいても、これCより楽だと思うんだけどなぁ。
CやEの方が正答者多いんだよなぁ。