TopCoder problem "Transformation" used in SRM 391 (Division I Level Three)



Problem Statement

    

You are to transform a positive integer vector (A1,A2,...,An) into another positive integer vector (B1,B2,...,Bn) of the same length. The transformation must satisfy the conditions below:

1) For 1 < = i < =n., Bi must evenly divide into Ai.

2) The least common multiple of all Ai should be equal to that of all Bi.

You are given the original integer vector as a String[] A, where the i-th (1-based) element is a positive integer representing Ai. Return a String[] containing the transformed integer vector in the same format. Each element of the return String[] must be a positive integer with no leading zeroes. If there are multiple solutions, return the one where the first number is the smallest. If there are still multiple solutions, return the one with the smallest second number etc.

 

Definition

    
Class:Transformation
Method:transform
Parameters:String[]
Returns:String[]
Method signature:String[] transform(String[] A)
(be sure your method is public)
    
 

Notes

-The least common multiple of a group of positive integers is the least positive integer which is a multiple of every integer in the group.
 

Constraints

-A will contain between 1 and 50 elements, inclusive.
-Each element of A will contain digits ('0' - '9') only.
-Each element of A will represent a positive integer without leading zeros.
-Each element of A will contain between 1 and 18 characters, inclusive.
 

Examples

0)
    
{"1","2"}
Returns: {"1", "2" }
1)
    
{"2","3","6"}
Returns: {"1", "1", "6" }
{1,1,6},{1,3,2},{1,3,6},{2,1,3},{2,1,6},{2,3,1},{2,3,2},{2,3,3},{2,3,6} are all transformation results.
2)
    
{"210","2","3","5","7"}
Returns: {"1", "2", "3", "5", "7" }
3)
    
{"6","2","3","4","9"}
Returns: {"1", "1", "1", "4", "9" }
4)
    
{"6","2","3","4","9","8"}
Returns: {"1", "1", "1", "1", "9", "8" }
5)
    
{"3637","260","26122993443584","47715564111559878","2","871126696052836","3492829317","83024857214176826"}
Returns: 
{"3637",
"5",
"26122993443584",
"7952594018593313",
"1",
"217781674013209",
"3492829317",
"41512428607088413" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8291

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11125&pm=8291

Writer:

stone

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Math