SRM 358 500pt : BalanceScale

keyword

最大公約数　動的計画法　C++

問題概要

整数列X(X[i]<10^7 = N、長さM<50)が与えられる。その中からいくつか選んで、選ばなかった全ての数が選んだ数の線型結合（のようなもの）で表されるようにしたい。最小いくつ選ぶ必要があるか求める問題。

解法

M=1のときは1。それ以外の時、まずgcd(X)を求めて全てXで割る。このとき、1が含まれていたら答えは1で、それ以外の時、SをXの部分集合とするとgcd(S)=1となる最小の濃度が答えになりそう（ax +byはgcd(x,y)の倍数になるとかから。最小性は示してない…）。
で、後は動的計画法で答えを求める。計算量は真面目に考えていないけど、多分O(N + M)位に収まってるはず。

#include <algorithm>
#include <vector>
using namespace std;

const int INF = 1<<29;

struct BalanceScale {

	int takeWeights(vector <int> weight) {
		int N = weight.size();
		if(N==1) return 1;

		int d = __gcd(weight[0], weight[1]);
		for(int i=2; i<N; i++){
			d = __gcd(d, weight[i]);
		}

		for(int i=0; i<N; i++){
			weight[i] /= d;
		}

		vector<int> ds(1 + *max_element(weight.begin(), weight.end()), INF);
		for(int i=0; i<N; i++) ds[weight[i]] = 1;
		for(int i=*max_element(weight.begin(), weight.end()); i > 1; i--)if(ds[i] < INF){
			for(int j=0; j<N; j++){
				int nd = __gcd(i, weight[j]);
				ds[nd] = min(ds[nd], ds[i] + 1);
			}
		}

		return ds[1];
	}

};