TopCoder problem "SumAndProduct" used in SRM 431 (Division II Level Three)



Problem Statement

    A list of non-negative numbers is called satisfactory if the sum of the numbers in the list is equal to S and the product of the numbers is equal to P. Find a satisfactory list with the least possible number of elements, and return its size. If no such list exists, return -1 instead. Please note that the list may contain non-integer numbers.
 

Definition

    
Class:SumAndProduct
Method:smallestSet
Parameters:int, int
Returns:int
Method signature:int smallestSet(int S, int P)
(be sure your method is public)
    
 

Constraints

-S and P will be between 1 and 1,000,000,000, inclusive.
 

Examples

0)
    
10
10
Returns: 1
The list contains only one element: 10.
1)
    
5
6
Returns: 2
The list contains two elements: 2 and 3.
2)
    
5
100
Returns: -1
No such list exists.
3)
    
100
1000000000
Returns: 9

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13522&pm=10257

Writer:

Gluk

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Math