lightoj1215

maksyuki 发表于 oj 分类,标签:
0

1215 - Finding LCM

You will be given a, b and L. You have to find c such that LCM (a, b, c) = L. If there are several solutions, print the one where c is as small as possible. If there is no solution, report so.LCM is an abbreviation used for Least Common Multiple in Mathematics. We say LCM (a, b, c) = L if and only if L is the least integer which is divisible by a, b and c.

Input

Input starts with an integer T (≤ 325), denoting the number of test cases.

Each case starts with a line containing three integers a b L (1 ≤ a, b ≤ 106, 1 ≤ L ≤ 1012).

Output

For each case, print the case number and the minimum possible value of c. If no solution is found, print 'impossible'.

Sample Input

Output for Sample Input

33 5 30209475 6992 770868002 6 10 Case 1: 2Case 2: 1Case 3: impossible

 

题目类型:素因子分解

算法分析:这是一道使用素因子分解求解LCM相关问题的典型例题。首先将a、b和L进行素因子分解,然后从小到大枚举判断L的每个素因子的指数值k,若a和b对应的指数值的最大值小于k,则c的对应的指数值就是k。若a和b对应的指数值的最大值等于k,则不需要进行任何操作。若大于k,则不可能出现这种情况,直接输出”impossible”即可。枚举完L的所有素因子之后,注意要查看此时a和b是否还有没在前面判断中出现的素因子。若还有,则也输出”impossible”。反之,则输出c的值