Codeforces #256 Div2 E. Divisors

Div2 Eにしてはやさしめな問題。
http://codeforces.com/contest/448/problem/E

問題

整数列Aに対する関数f(A)がある。
f(A)はAの各要素に対し、その約数を昇順に並べたものに置き換え、数列の数列をflattenした状態にするものである。

ここで初期値X、数Kが与えられる。
整数列A=[X]に対し、f^K(A)を列挙せよ。ただしf^K(A)が10^5要素を超えるなら先頭10^5要素だけで良い。

解法

f(A)には以下の特性がある。

• 要素1に対し関数fを適用しても何も変わらない。
• 2以上の要素に対し関数fを適用すると、最初に1が来る。

よって、X==1ならKの値を問わず1が1つのみ、X>1なら先頭に1がK個以上来るので、K>=10^5の時は容易に答えが出る。

後は事前にXの約数や、約数の約数を列挙しておき、10^5要素たまるまでDFSでf^K([X])の値を出力すればよい。

ll X,K;
vector<ll> V,V2[10000];
vector<ll> R;
map<ll,int> M;

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

void dodo(ll v,ll k) {
	if(k==0) {
		if(R.size()<100000) R.push_back(v);
		return;
	}
	int i,x=M[v];
	FOR(i,V2[x].size()) {
		if(R.size()>=100000) return;
		if(V2[x][i]==1) R.push_back(1);
		else dodo(V2[x][i],k-1);
	}
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>X>>K;
	if(X==1) return _P("1\n");
	if(K>=100000) {
		FOR(i,100000) _P("1 ");
		return _P("\n");
	}
	V=enumdiv(X);
	FOR(i,V.size()) {
		M[V[i]]=i;
		V2[i]=enumdiv(V[i]);
	}
	
	dodo(X,K);
	x=min((int)R.size(),100000);
	FOR(i,x) _P("%lld ",R[i]);
	_P("\n");
}

まとめ

解き方は普通だけど、発想は面白い問題。