【Codeforces 703E】Mishka and Divisors

题目传送门：http://codeforces.com/contest/703/problem/E
官方题解：http://codeforces.com/blog/entry/46434
中文题面：http://www.cnblogs.com/dramstadt/p/5759206.html

题解的话，看官方题解就好
唯一想吐槽的就是：CF上居然卡常！
看看这通过的名单，™大家都是压线过的啊

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int M = 7000;
const int N = 1000+9;
const int INF = 10000000;

LL k,Hash[M],buf[M],sum[2][M];
int n,cnt,f[2][M],nxt[N][M],vout[N][M];
unordered_map<LL,int> idx;

inline LL read(){
	char c=getchar(); LL ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

inline LL find(LL w){
	int l=1, r=cnt, mid;
	while (l <= r) {
		mid = l + r >> 1;
		if (Hash[mid] == w) return mid;
		else if (Hash[mid] < w) l = mid+1;
		else r = mid-1;
	} 
}

inline void Decomposision(LL num) {
	LL lim = sqrt(num); if (lim*lim != num) lim++;
	for (int i=1;i<=lim;i++) if (num % i == 0) buf[++cnt] = i, buf[++cnt] = num/i;
	if (lim*lim == num) cnt--;
	for (int i=1;i<=cnt;i++) Hash[i] = buf[i];
	sort(Hash+1,Hash+1+cnt);
	for (int i=1;i<=cnt;i++) idx[buf[i]] = find(buf[i]);
}

inline LL GCD(LL a, LL b){
	while (b) {
		a = a%b;
		swap(a, b);
	}
	return a;
}

inline void SPJ(){
	if (k == 1) {
		LL vout = 1, tmp = read();
		for (int i=2;i<=n;i++) {
			LL t1 = read(); if (t1 < tmp) 
			tmp = t1, vout = i;
		} cout<<1<<endl<<vout; exit(0);
	}
}

int main(){
	n = read(); k = read(); SPJ();
	Decomposision(k); 
	for (int i=2;i<=cnt;i++) f[0][i] = INF; int now=1,pre=0;
	for (int i=1;i<=n;i++,pre^=1,now^=1) {
		LL w = read(), t2, t3 = GCD(w,k);
		for (int j=2,tmp,t1;j<=cnt;j++) {
			tmp = f[pre][t1=idx[Hash[j]/GCD(Hash[j],t3)]]+1;
			t2 = w + sum[pre][t1];
			if (f[pre][j] > tmp  || (f[pre][j] == tmp && t2 <= sum[pre][j])) 
				f[now][j] = tmp, nxt[i][j] = t1, vout[i][j] = i, sum[now][j] = t2;
			else f[now][j] = f[pre][j], nxt[i][j] = j, vout[i][j] = 0, sum[now][j] = sum[pre][j];
		}
	}
	if (f[pre][cnt] == INF) printf("-1\n");
	else {
		printf("%d\n",f[pre][cnt]);
		LL w = cnt, stp = n;
		while (w) {
			if (vout[stp][w]) printf("%d ",vout[stp][w]);
			w = nxt[stp][w]; stp--;
		}
	}
	return 0;
}