[POI2012] ODL-Distance
题目描述
We consider the distance between positive integers in this problem, defined as follows.
A single operation consists in either multiplying a given number by a prime number1 or dividing it by a prime number (if it does divide without a remainder).
The distance between the numbers ![](http://main.edu.pl/images/OI19/odl-en-tex.1.png) and ![](http://main.edu.pl/images/OI19/odl-en-tex.2.png), denoted ![](http://main.edu.pl/images/OI19/odl-en-tex.3.png), is the minimum number of operations it takes to transform the number ![](http://main.edu.pl/images/OI19/odl-en-tex.4.png) into the number ![](http://main.edu.pl/images/OI19/odl-en-tex.5.png).
For example, ![](http://main.edu.pl/images/OI19/odl-en-tex.6.png).
Observe that the function ![](http://main.edu.pl/images/OI19/odl-en-tex.7.png) is indeed a distance function - for any positive integers ![](http://main.edu.pl/images/OI19/odl-en-tex.8.png), ![](http://main.edu.pl/images/OI19/odl-en-tex.9.png) and ![](http://main.edu.pl/images/OI19/odl-en-tex.10.png) the following hold:
the distance between a number and itself is 0: ![](http://main.edu.pl/images/OI19/odl-en-tex.11.png), the distance from ![](http://main.edu.pl/images/OI19/odl-en-tex.12.png) to ![](http://main.edu.pl/images/OI19/odl-en-tex.13.png) is the same as from ![](http://main.edu.pl/images/OI19/odl-en-tex.14.png) to ![](http://main.edu.pl/images/OI19/odl-en-tex.15.png): ![](http://main.edu.pl/images/OI19/odl-en-tex.16.png), and the triangle inequality holds: ![](http://main.edu.pl/images/OI19/odl-en-tex.17.png).
A sequence of ![](http://main.edu.pl/images/OI19/odl-en-tex.18.png) positive integers, ![](http://main.edu.pl/images/OI19/odl-en-tex.19.png), is given.
For each number ![](http://main.edu.pl/images/OI19/odl-en-tex.20.png) we have to determine ![](http://main.edu.pl/images/OI19/odl-en-tex.21.png) such that ![](http://main.edu.pl/images/OI19/odl-en-tex.22.png) and ![](http://main.edu.pl/images/OI19/odl-en-tex.23.png) is minimal.
给你一个序列a[],定义d(i,j)=a[i],a[j]每次操作可以对其中之一乘一个质数p或除以一个数p(p必须为被除数的约数),让a[i]=a[j]的最少操作步数
对于每个i,求d(i,j)最小的j,若有多个解,输出最小的j
输入输出格式
输入格式
In the first line of standard input there is a single integer ![](http://main.edu.pl/images/OI19/odl-en-tex.24.png) (![](http://main.edu.pl/images/OI19/odl-en-tex.25.png)).
In the following ![](http://main.edu.pl/images/OI19/odl-en-tex.26.png) lines the numbers ![](http://main.edu.pl/images/OI19/odl-en-tex.27.png) (![](http://main.edu.pl/images/OI19/odl-en-tex.28.png)) are given, one per line.
In tests worth 30% of total point it additionally holds that ![](http://main.edu.pl/images/OI19/odl-en-tex.29.png).
输出格式
Your program should print exactly ![](http://main.edu.pl/images/OI19/odl-en-tex.30.png) lines to the standard output, a single integer in each line.
The ![](http://main.edu.pl/images/OI19/odl-en-tex.31.png)-th line should give the minimum ![](http://main.edu.pl/images/OI19/odl-en-tex.32.png) such that: ![](http://main.edu.pl/images/OI19/odl-en-tex.33.png), ![](http://main.edu.pl/images/OI19/odl-en-tex.34.png) and ![](http://main.edu.pl/images/OI19/odl-en-tex.35.png) is minimal.
输入输出样例
输入样例 #1
6
1
2
3
4
5
6
输出样例 #1
2
1
1
2
1
2
说明
给你一个序列a[],定义d(i,j)=a[i],a[j]每次操作可以对其中之一乘一个质数p或除以一个数p(p必须为被除数的约数),让a[i]=a[j]的最少操作步数
对于每个i,求d(i,j)最小的j,若有多个解,输出最小的j