RCC 2014 Warmup - Div1 C. Square Table

面白い問題だった。
http://codeforces.com/contest/418/problem/C

問題

数N,Mが与えられるので、以下の条件を満たすNxMの行列を返せ。

• 各要素は1～10^8の整数
• 各行について、行内各要素の二乗和を取ると平方数である
• 各列について、列内各要素の二乗和を取ると平方数である

解法

二乗和を取ると平方数となるような整数群があったとすると、全体を整数倍してもやはり二乗和は平方数となる。
例えば3^2+4^2+12^2+84^2 = 85^2なら、全体を２倍しても2^2*(3^2+4^2+12^2+84^2)=(2*85)^2で成り立つ。

よって、N要素の整数群とM要素の整数群を掛け合わせればよい。
例えば４要素なら先の3^2+4^2+12^2+84^2=85^2、３要素なら2^2+3^2+6^2=7^2なのでこんな感じでNxMの行列を生成できる。

   3  4 12  84
 -------------
2| 6  8 24 168
3| 9 12 36 252
6|18 24 72 504

問題は、N要素とM要素の整数群を求めることである。
幸い、1～100要素については2要素以外は1と2と3だけで生成できるので、総当たりで候補を探せばよい。
2要素の時は(3,4)を用いる。

int N,M;
vector<int> MM[101];
void solve() {
	int f,i,j,k,l,x,y,z;
	
	cin>>N>>M;
	MM[1].push_back(1);
	MM[2].push_back(3);
	MM[2].push_back(4);
	FOR(x,101) FOR(y,101) FOR(z,101) {
		if(x+y+z>=3 && x+y+z<=100) {
			int hoge=x+y*4+z*9;
			int aa=sqrt(hoge+0.1);
			while(aa*aa<hoge)aa++;
			while(aa*aa>hoge)aa--;
			while(aa*aa<hoge)aa++;
			while(aa*aa>hoge)aa--;
			if(aa*aa==hoge && MM[x+y+z].empty()) {
				FOR(i,x) MM[x+y+z].push_back(1);
				FOR(i,y) MM[x+y+z].push_back(2);
				FOR(i,z) MM[x+y+z].push_back(3);
			}
		}
	}
	FOR(y,N) {
		FOR(x,M) _P("%d ",MM[N][y]*MM[M][x]);
		_P("\n");
	}
}

まとめ

本番気が付けてよかった。