3857. 因数串

单点时限: 1.0 sec

内存限制: 512 MB

Cuber QQ 沉迷数学研究,最近他在研究数的因数,并发明了因数串。

因数的概念是,如果整数 $a$ 除以整数 $b(b\neq 0)$ 的商正好是整数而没有余数,我们就说 $b$ 是 $a$ 的因数。

因数串,指的是由正整数 $a$ 所有因数所构成的一个数列,需要满足从数列的第 $2$ 个数开始,每个数都必须由其前一个数乘以某个质数或除以某个质数得出的。

因数串需要保证正整数 $a$ 所有因数都会出现且只出现一次。现在 Cuber QQ 会告诉你正整数 $a$ ,你需要给出任意一个因数串。

输入格式

输入数据第一行包含一个正整数 $n$ ($1\le n\le 14$) ,表示 $a$ 的质因数个数。

接下来 $n$ 行,每行两个整数 $p_i,k_i$ ($1\le p_i\le 10^{18},1\le k_i\le 60$) ,其中 $p_i$ 一定是质数,且两两都不相同。

其中正整数 $a=\prod _ {i=1} ^ n p_i ^ {k_i} $ ,输入数据保证 $2\le a\le 10^{18}$ 且 $\prod _ {i=1} ^ n (k_i+1) \le 40000 $ 。

输出格式

输出数据包含若干行,每行一个整数,按照顺序依次输出正整数 $a$ 的因数串。

样例

Input
2
2 3
3 2
Output
1
2
4
8
24
12
6
3
9
18
36
72

302 人解决,422 人已尝试。

334 份提交通过,共有 1126 份提交。

2.7 EMB 奖励。

创建: 9 月,3 周前.

修改: 9 月,1 周前.

最后提交: 1 月前.

来源: N/A

题目标签