当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3993:Not So Flat After All

题目描述
Any positive integer v can be written as p1a1*p2a2*...*pnan where pi is a prime number and ai ≥ 0. For example: 24 = 23*31.
Pick any two prime numbers p1 and p2 where p1 = p2. Imagine a two dimensional plane where the powers of p1 are plotted on the x-axis and the powers of p2 on the y-axis. Now any number that can be written as p1a1*p2a2 can be plotted on this plane at location (x, y) = (a1, a2). The figure on the right shows few examples where p1 = 3 and p2 = 2.

This idea can be extended for any N-Dimensional space where each of the N axes is assigned a unique prime number. Each N-Dimensional space has a unique set of primes.
We call such set the Space Identification Set or S for short. |S| (the ordinal of S) is N.
Any number that can be expressed as a multiplication of pi ∈ S (each raised to a power (ai ≥ 0) can be plotted in this |S|-Dimensional space. The figure at the bottom illustrates this idea for N = 3 and S = {2, 3, 7}. Needless to say, any number that can be plotted on space A can also be plotted on space B as long as SA __poj_jax_start__\subset__poj_jax_end__\subset SB.
We define the distance between any two points in a given N-Dimensional space to be the sum of units traveled to get from one point to the other while following the grid lines (i.e. movement is always parallel to one of the axes.) For example, in the figure below, the distance between 168 and 882 is 4.
Given two positive integers, write a program that determines the minimum ordinal of a space where both numbers can be plotted in. The program also determines the distance between these two integers in that space.
输入解释
Your program will be tested on one or more test cases. Each test case is specified on a line with two positive integers (0 < A,B < 1, 000, 000) where A * B > 1.
The last line is made of two zeros.
输出解释
For each test case, print the following line:
k. X:D
Where k is the test case number (starting at one,) X is the minimum ordinal needed in a space that both A and B can be plotted in. D is the distance between these two points.
输入样例
168 882
770 792
0 0
输出样例
1. 3:4
2. 5:6

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 anarc 2009

源链接: POJ-3993

最后修改于 2020-10-29T07:17:38+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536