#include <utility>
#include <vector>
std::vector< std::pair<int, int> > factor_table;
void fill_sieve( int n )
{
factor_table.resize(n+1);
for( int i = 1; i <= n; ++i )
factor_table[i] = std::pair<int, int>(i, 1);
for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
if (factor_table[j].second == 1) {
int i = j;
int ij = j2;
while (ij <= n) {
factor_table[ij] = std::pair<int, int>(j, i);
++i;
ij += j;
}
}
}
}
std::vector<unsigned> powers;
template<int dir>
void factor( int num )
{
while (num != 1) {
powers[factor_table[num].first] += dir;
num = factor_table[num].second;
}
}
void calc_catalan(unsigned N)
{
powers.resize(N+1);
for( unsigned k = 2; k <= N; ++k ) {
factor<+1>(k+N);
factor<-1>(k);
}
}
#include <iostream>
#include <cmath>
int main(void)
{
fill_sieve(20000);
unsigned N = 9913;
calc_catalan(N);
char* sep = "";
for( unsigned i = 0; i < powers.size(); ++i ) {
if (powers[i]) {
std::cout << sep << i;
sep = " * ";
if (powers[i] > 1)
std::cout << "**" << powers[i];
}
}
std::cout << "\n\n";
}
I2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDx2ZWN0b3I+CgpzdGQ6OnZlY3Rvcjwgc3RkOjpwYWlyPGludCwgaW50PiA+IGZhY3Rvcl90YWJsZTsKdm9pZCBmaWxsX3NpZXZlKCBpbnQgbiApCnsKCWZhY3Rvcl90YWJsZS5yZXNpemUobisxKTsKCWZvciggaW50IGkgPSAxOyBpIDw9IG47ICsraSApCgkJZmFjdG9yX3RhYmxlW2ldID0gc3RkOjpwYWlyPGludCwgaW50PihpLCAxKTsKCWZvciggaW50IGogPSAyLCBqMiA9IDQ7IGoyIDw9IG47IChqMiArPSBqKSwgKGoyICs9ICsraikgKSB7CgkJaWYgKGZhY3Rvcl90YWJsZVtqXS5zZWNvbmQgPT0gMSkgewoJCQlpbnQgaSA9IGo7CgkJCWludCBpaiA9IGoyOwoJCQl3aGlsZSAoaWogPD0gbikgewoJCQkJZmFjdG9yX3RhYmxlW2lqXSA9IHN0ZDo6cGFpcjxpbnQsIGludD4oaiwgaSk7CgkJCQkrK2k7CgkJCQlpaiArPSBqOwoJCQl9CgkJfQoJfQp9CgpzdGQ6OnZlY3Rvcjx1bnNpZ25lZD4gcG93ZXJzOwoKdGVtcGxhdGU8aW50IGRpcj4Kdm9pZCBmYWN0b3IoIGludCBudW0gKQp7Cgl3aGlsZSAobnVtICE9IDEpIHsKCQlwb3dlcnNbZmFjdG9yX3RhYmxlW251bV0uZmlyc3RdICs9IGRpcjsKCQludW0gPSBmYWN0b3JfdGFibGVbbnVtXS5zZWNvbmQ7Cgl9Cn0KCnZvaWQgY2FsY19jYXRhbGFuKHVuc2lnbmVkIE4pCnsKICAgIHBvd2Vycy5yZXNpemUoTisxKTsKICAgIGZvciggdW5zaWduZWQgayA9IDI7IGsgPD0gTjsgKytrICkgewogICAgICAgICBmYWN0b3I8KzE+KGsrTik7CiAgICAgICAgIGZhY3RvcjwtMT4oayk7CiAgICB9Cn0KCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGNtYXRoPgppbnQgbWFpbih2b2lkKQp7CiAgICBmaWxsX3NpZXZlKDIwMDAwKTsKICAgIHVuc2lnbmVkIE4gPSA5OTEzOwogICAgY2FsY19jYXRhbGFuKE4pOwogICAgY2hhciogc2VwID0gIiI7CiAgICBmb3IoIHVuc2lnbmVkIGkgPSAwOyBpIDwgcG93ZXJzLnNpemUoKTsgKytpICkgewogICAgCWlmIChwb3dlcnNbaV0pIHsKICAgIAkgICAgc3RkOjpjb3V0IDw8IHNlcCA8PCBpOwogICAgCSAgICBzZXAgPSAiICogIjsKICAgIAkgICAgaWYgKHBvd2Vyc1tpXSA+IDEpCiAgICAJICAgICAgICBzdGQ6OmNvdXQgPDwgIioqIiA8PCBwb3dlcnNbaV07CiAgICAJfQogICAgfQogICAgc3RkOjpjb3V0IDw8ICJcblxuIjsKfQ==