TopCoder SRM 577 Div2 Hard EllysCoprimesDiv2

Div1 Mediumはまだ解けてないので先にDiv2 Hardから。
http://community.topcoder.com/stat?c=problem_statement&pm=12461

問題

整数列が与えられる。
この整数列をソートした後、隣接要素同士が互いに素になるようにしたい。
素にならない場合、間に数値を加えることで素にしていく場合、条件を満たす整数列の最小要素数を答える。

解法

まず数列をソートし、隣接要素を比較する。
隣接要素同士がすでに互いに素なら、間に要素を挿入する必要はない。
素で無いなら、総当たりで間に１個数値を挟んで両者に素となるものを探す。
そのようなものが無い場合、間に２個はさめば確実に隣接要素および挿入した２要素が素になるものがある。

…これで通っちゃったんだけど、間に２個はさめば十分って証明はできなかった。
TopCoder Forumsでも色々議論されてるけど、まだ確定的な証明は出てないな。Editorial待ちか。

class EllysCoprimesDiv2 {
	public:
	int gcd(int a, int b) { return (b==0)?a:gcd(b,a%b);}

	int cop(int A,int B) {
		int i;
		if(gcd(A,B)==1) return 0;
		for(i=A+1;i<B;i++) if(gcd(A,i)==1 && gcd(i,B)==1) return 1;
		return 2;
	}
	
	int getCount(vector <int> numbers) {
		int n=0,i;
		sort(numbers.begin(),numbers.end());
		FOR(i,numbers.size()-1) n+=cop(numbers[i],numbers[i+1]);
		return n;
	}
};

まとめ

間に２個はさめばよい、って直感でやっちゃったけどいいのかなこれ。
他にも同じ人は多かったみたいだけど…。