Codeforces #365 Div2 E. Mishka and Divisors

これTL2秒でいいと思うんだけどな。
http://codeforces.com/contest/703/problem/E

問題

N要素の数列A[i]が与えられる。
ここからいくつかの要素を選び、その積がKの倍数になるようにしたい。
条件を満たす要素の選び方の一例を求めよ。

ただし条件を満たす選び方が複数ある場合、選ぶ要素数を最小化せよ。
また選ぶ要素数がタイになる場合、要素の和が小さい方を選べ。

解法

A[i]の積を直接求めるのは大変だが、結局Kの倍数かどうかだけ分かればいいので積をすべて持つ必要はない。
GCD(K,A[i]のうち選んだものの積)だけを管理すればよい。

当然上記GCDの値はKの約数になる。
Kは10^12以下なので、Wikipediaなどの高度合成数の項を見ると約数は7000個もないことが分かる。

まずKの約数を列挙したうえで以下を求めよう。
f(n,k) := A[0...n]からいくつか要素を選択したとき、選択要素の積とKのGCDはKの約数のうち小さい方からk番目となるような選択の仕方のうちで、要素数最小・和が最小のものの(要素数,和,直前に選択した要素)のタプル
nは1000以下、kは7000以下で、要素は選ぶ選ばないの２通りしか遷移がないのでかろうじて1秒で間に合う。
DPを終えたらそれを巻き戻して選択した要素を列挙すればよい。

注意点として、(Kのk番目の約数をpとしたとき)f(n,k)から次のDPの過程でGCD(p*A[n],K)を求める処理がある。
この場合p*A[n]が64bitでもオーバーフローしかねない。
この場合、先にK/pを求めておいてp*GCD(A[n],K/p)とするとオーバーフローを回避できる。

vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for(ll i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	return S;
}

int N;
ll K;
ll A[10101];
unordered_map<ll,int> U;
int num[1010][7000];
ll sum[1010][7000];
int from[1010][7000];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	if(K==1) {
		FOR(i,N) cin>>A[i];
		cout<<1<<endl;
		cout<<1+(min_element(A,A+N)-A)<<endl;
		return;
	}
	
	auto V=enumdiv(K);
	auto VR=V;
	reverse(ALL(VR));
	
	FOR(i,V.size()) U[V[i]]=i, num[0][i]=101010;
	
	num[0][0]=0;
	FOR(x,N) {
		ll X;
		cin>>X;
		
		FOR(i,V.size()) {
			num[x+1][i]=num[x][i];
			sum[x+1][i]=sum[x][i];
			from[x+1][i]=i;
		}
		
		FOR(i,V.size()) if(num[x][i]<1010) {
			int zi=U[V[i]*__gcd(X,VR[i])];
			if(num[x+1][zi]>num[x][i]+1 || (num[x+1][zi]==num[x][i]+1 && sum[x+1][zi]>sum[x][i]+X)) {
				num[x+1][zi]=num[x][i]+1;
				sum[x+1][zi]=sum[x][i]+X;
				from[x+1][zi]=i;
			}
		}
	}
	x = U.size()-1;
	if(num[N][x]>N) return _P("-1\n");
	
	vector<int> R;
	for(y=N;y>0;y--) if(from[y][x]!=x) {
		R.push_back(y);
		x=from[y][x];
	}
	
	_P("%d\n",R.size());
	FORR(r,R) _P("%d ",r);
	_P("\n");
	
}

まとめ

この問題は最後のDPを復元するパート要る…？