AOJ1069 Squid Multiplication

問題リンク Squid Multiplication

• 解法

a0を頑張って特定します。a0が決まると、数列Bの中の偶数のものをa0で割ることで数列Aの奇数が作り出せます。
数列Bの2つの偶数のものbi, bjは
bi = a0 * ai
bj = a0 * aj
となっています。また、Bの中の奇数の中にはai*ajとなっているbkがあるはずです。
bk = ai * aj
これらから、
bi * bj / bk = a0^2
という式が導けます。
よって、適当な奇数を1つ選んでbkとし、biとbjの組み合わせを全て選んでa0を作り、このa0から数列Bを復元できるかを調べれば解けます。
偶数の項は必ずN個だけあるので、調べる組み合わせはN*(N-1)/2個です。
bi*bj/bkを計算するときに、そのまま掛け算するとlongでもオーバーフローするのでgcdをとって項を小さくする必要があります。biとbjが正しい組み合わせなら演算結果がオーバーフローすることはないので解となるa0が正しく求まります。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

//Squid Multiplication
public class AOJ1069 {

	long gcd(long a, long b){
		return b==0?a:gcd(b, a%b);
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			List<Long> even = new ArrayList<Long>(), odd = new ArrayList<Long>(), list = new ArrayList<Long>();
			for(int i=0;i<n*(n+1)/2;i++){
				long x = sc.nextLong();
				list.add(x);
				if(x%2==0)even.add(x);
				else odd.add(x);
			}
			Collections.sort(list);
			boolean con = true;
			for(int i=0;i<even.size()&&con;i++)for(int j=i+1;j<even.size()&&con;j++){
				long bi = even.get(i), bj = even.get(j), bk = odd.get(0);
				long g = gcd(bi, bk);
				bi/=g; bk/=g;
				g = gcd(bj, bk);
				bj/=g; bk/=g;
				double r = Math.sqrt(bi*bj/bk);
				long a0 = (long)r;
				if(a0==0)continue;
				long[] a = new long[n];
				boolean f = true;
				List<Long> l = new ArrayList<Long>();
				for(int x=0;x<n;x++){
					long y = even.get(x);
					if(y%a0!=0){
						f = false; break;
					}
					a[x]=even.get(x)/a0;
					l.add(a0*a[x]);
				}
				if(!f)continue;
				for(int x=0;x<n;x++)for(int y=x+1;y<n;y++)l.add(a[x]*a[y]);
				Collections.sort(l);
				boolean ok = true;
				for(int x=0;x<l.size();x++){
					long A = l.get(x), B = list.get(x);
					if(A!=B){
						ok = false; break;
					}
				}
				if(ok){
					Arrays.sort(a);
					System.out.println(a0);
					con = false;
					for(int x=0;x<n;x++)System.out.print(a[x]+(x==n-1?"\n":" "));
				}
			}
		}

	}

	public static void main(String[] args) {
		new AOJ1069().run();
	}
}