DivisorInc
SRM 302 · 2006-05-11 · by Andrew_Lazarev
Problem Statement
There is an integer K. You are allowed to add to K any of its divisors not equal to 1 and K. The same operation can be applied to the resulting number and so on. Notice that starting from the number 4, we can reach any composite number by applying several such operations. For example, the number 24 can be reached starting from 4 using 5 operations: 4->6->8->12->18->24.
You will solve a more general problem. Given
Constraints
- N will be between 4 and 100000, inclusive.
- M will be between N and 100000, inclusive.
4 24 Returns: 5
The example from the problem statement.
4 576 Returns: 14
The shortest order of operations is: 4->6->8->12->18->27->36->54->81->108->162->243->324->432->576.
486 7128 Returns: 9
The shortest order of operations is: 486->729->972->1458->2187->2916->4374->6561->6804->7128
8748 83462 Returns: 10
The shortest order of operations is: 8748->13122->19683->26244->39366->59049->78732->83106->83448->83460->83462.
235 98234 Returns: 21
4 99991 Returns: -1
The number 99991 can't be obtained because it is prime.
82736 82736 Returns: 0
We don't need any operations. N and M are already equal.
Submissions are judged against all 154 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DivisorInc with a public method int countOperations(int N, int M) · 154 test cases · 2 s / 256 MB per case