#P3532. [POI 2012] ODL-Distance
[POI 2012] 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 and
, denoted
, is the minimum number of operations it takes to transform the number
into the number
.
For example, .
Observe that the function is indeed a distance function - for any positive integers
,
and
the following hold:
the distance between a number and itself is 0: , the distance from
to
is the same as from
to
:
, and the triangle inequality holds:
.
A sequence of positive integers,
, is given.
For each number we have to determine
such that
and
is minimal.
输入格式
In the first line of standard input there is a single integer (
).
In the following lines the numbers
(
) are given, one per line.
In tests worth 30% of total point it additionally holds that .
输出格式
Your program should print exactly lines to the standard output, a single integer in each line.
The -th line should give the minimum
such that:
,
and
is minimal.
题目大意
题目描述
译自 POI 2012 Stage 1. 「Distance」
定义一次「操作」为将一个正整数除以或乘以一个质数。定义函数 表示将 进行若干次“操作”变成 所需要的最小操作次数。例如,.
显然是一个距离函数,满足以下性质:
给定 个正整数 ,对每个 ,求 使得 且 最小。如果有多个满足条件的 ,应输出最小的那个。
输入格式
第一行一个正整数 .
第二行 个正整数 .
输出格式
输出 行,每行一个整数,表示使 且 最小的 .
数据范围
对于 的数据有 .
对于所有数据有 .
翻译来自于 LibreOJ。
6
1
2
3
4
5
6
2
1
1
2
1
2