#P2790. [Poi2012]Distance

    ID: 1898 传统题 1000ms 512MiB 尝试: 422 已通过: 171 难度: 7 上传者: 标签>CF2200提高+/省选-倍数枚举线性筛最小值与次小值优化转移鸣谢

[Poi2012]Distance

题目描述

对正整数进行一次操作时,可以选择一个质数 pp,将当前数乘以 pp,或者在 pp 整除当前数时将其除以 pp。定义 d(a,b)d(a,b) 为将 aa 变为 bb 所需的最少操作次数。例如,d(69,42)=3d(69,42)=3。

给定 nn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_n。对每个 ii,求满足 j≠ij\ne i 且 d(ai,aj)d(a_i,a_j) 最小的 jj。如果有多个这样的 jj,输出最小的那个。

输入格式

第一行一个整数 nn。

接下来输入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。原赛样例将它们分行给出。

输出格式

输出 nn 行,第 ii 行为位置 ii 的答案。

6
1
2
3
4
5
6
2
1
1
2
1
2

数据范围

2≤n≤1052\le n\le10^5,1≤ai≤1061\le a_i\le10^6。原赛 30% 的数据满足 n≤1000n\le1000。

POI 2012 官方题面及题解