d663. 11730 - Number Transformation
Tags :
Accepted rate : 165人/229人 ( 72% ) [非即時]

最近更新 : 2010-03-23 14:38


You are given an integer number S. You can transform any integer number A to another integer number B by adding x to A. This x is an integer number which is a prime factor of A (Please note that 1 and A are not being considered as a factor of A). Now, your task is to find the minimum number of transformations required to transform S to another integer number T.


EX: 6 12

6->9->12   2次

6->8-> 10->12 3次


For each test case, there will be a line with two integers, S (1<=S<=100) & T (1<=T<=1000), as described above. The last test case will be followed by a line with two 0 s denoting end of output. This case should not be processed.

每組測資都有兩的數字S (1<=S<=100) & T (1<=T<=1000),

兩個0代表結束,不用輸出任何數字 。


For every test case except the last one, print a line of the form “Case X: Y” where X is the serial number of output (starting from 1). Y is the minimum number of transformations required to transform S to T. If it is not possible to make T from S with the given rules, Y shall be -1.

對於每個一個測資,除了0 0以外 ,請應出 “Case X: Y”,X從1開始算起,Y為S轉換到T的最小次數,若是無法轉換成功請書出-1

Sample Input #1
6 12
6 13
0 0
Sample Output #1
Case 1: 2
Case 2: -1
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <1M
Hint :
UVa11730 [管理者: snail(蝸牛) ]

ID User Problem Subject Hit Post Date
30037 dfd8282@gmai...(fishhh) d663
291 2022-04-23 18:24
29786 seer.2892108...(james lyu) d663
246 2022-04-01 01:00