AOJ 1069 Squid Multiplication (UAPC Problem: H)

ICPCの国内予選を突破できなかったので悔しくてねむれない．

それはともかくとして，とりあえずといたのでメモ程度に．

問題概略

n個の奇数と1個の偶数から構成される配列aがあるよ．

配列の中から2つ選んで積をとって配列bの要素にするよ．

配列aを求めてちょ．

解法

配列bで1番小さい偶数e1，2番目に小さい偶数e2，1番小さい奇数o1をとりだす．

e1 * e2 / o1 = 配列aの偶数の自乗　であることがわかる．

配列aの偶数x，1番小さい奇数y，2番目に小さい奇数zとすると，

e1 = x * y
e2 = x * z
o1 = y * z

e1 * e2 = x * x * y * z
e1 * e2 / o1 = x * x * y * z / (y * z) = x * x

ということで，xが求められるので偶数だけ選んでxで割ったら奇数の要素が計算できる．

ふつーにソース書いてふつーにランタイムエラーが出て，なんだろうかと思っていたら，long long と書くべき所にintって書いてた．

恥ずかしいソースコード

#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define MAX_N 256
#define MAX_A 40000
using namespace std;

long long gcd(long long x, long long y){
	return y == 0 ? x: gcd(y, x%y);
}

int n, m;
long long b[MAX_A];
int a[MAX_N];

void solve(){
	vector<long long> e, o;
	long long c1, c2, c3, g;
	for(int i=0;i<m;++i){
		if(b[i] % 2 == 0){
			e.push_back(b[i]);
		}
		else{
			o.push_back(b[i]);
		}
	}
	sort(e.begin(), e.end());
	sort(o.begin(), o.end());
	c1 = e[0]; c2 = e[1]; c3 = o[0];
	g = gcd(c1, c3);
	a[0] = (int)sqrt(c1 / g * (c2 / (c3 / g)));
	for(int i=0;i<n;++i){
		a[i+1] = (int)(e[i] / a[0]);
	}
	for(int i=0;i<=n;++i){
		printf("%d%s", a[i], (i == n || i == 0) ? "\n": " ");
	}
}

int main(){
	for(;;){
		scanf("%d", &n);
		if(n == 0) return 0;
		m = n*(n+1)/2;
		for(int i=0;i<m;++i){
			scanf("%lld", &b[i]);
		}
		solve();
	}
}

最大公約数をとっているのはオーバーフローを防ぐため．

大きいやつから順にとってもおなじようなことができると思うんだ．