BigFatInteger
SRM 599 · 2013-06-25 · by evima
Problem Statement
This problem statement contains superscipts that may not display properly outside the applet.
Lun the dog loves very large integers. Her favorite is AB (A to the power of B).
She has an integer variable X. Initially, the value of X is set to 1. She can perform the following two kinds of operations in any order, any number of times.
- Operation 1: choose a prime number p, then multiply X by p.
- Operation 2: choose a positive divisor d of the value of X at that point, then multiply X by d.
You are given two
Constraints
- A will be between 2 and 1,000,000 (106), inclusive.
- B will be between 1 and 1,000,000 (106), inclusive.
6 1 Returns: 2
Here, AB = 61 = 6. Here is one of the optimal sequences of operations: Perform operation 1 by choosing p=2. X is now 1*2 = 2. Perform operation 1 by choosing p=3. X is now 2*3 = 6.
162 1 Returns: 4
One of the optimal sequences of operations: Perform operation 1 by choosing p=3. X is now 1*3 = 3. Perform operation 1 by choosing p=3. X is now 3*3 = 9. Perform operation 2 by choosing d=9. X is now 9*9 = 81. Perform operation 1 by choosing p=2. X is now 81*2 = 162.
999983 9 Returns: 5
Here, A is prime. One of the optimal sequences of operations: Perform operation 1 by choosing p=A. X is now A. Perform operation 1 by choosing p=A. X is now A2. Perform operation 1 by choosing p=A. X is now A3. Perform operation 2 by choosing d=A3. X is now A6. Perform operation 2 by choosing d=A3. X is now A9.
360 8 Returns: 8
524288 1000000 Returns: 26
Submissions are judged against all 180 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BigFatInteger with a public method int minOperations(int A, int B) · 180 test cases · 2 s / 256 MB per case