NumericalPerfectionLevel
SRM 444 · 2009-07-08 · by vexorian
Problem Statement
We define the perfection level of a positive integer N as k if N can be expressed as a product of 4 positive integers, each with a perfection level of at least (k-1), and cannot be expressed as a product of 4 positive integers, each with a perfection level greater than (k-1). There is one exception - if it is not possible to express N as a product of 4 positive integers all greater than 1, then the perfection level of N is 0.
Given a
Constraints
- N will be between 1 and 10000000000000 (10^13), inclusive.
4 Returns: 0
4 cannot be expressed as a product of 4 numbers all greater than 1.
144 Returns: 1
144 = 4 x 2 x 3 x 6 The level of 4, 2, 3 and 6 is 0.
1152 Returns: 1
One of many possible ways to express 1152 is: 1152 = 144 x 2 x 2 x 2 Although 144's level is 1, the remaining factors are of level 0. There is no way to express 1152 as a product of four level 1 numbers.
1679616 Returns: 2
1679616 = 36 x 36 x 36 x 36 36 = 2 x 2 x 3 x 3
10000000000000 Returns: 2
999999999112 Returns: 1
Times out if i is int and not long.
9971252437441 Returns: 1
Large 4th power of a prime.
9999999999001 Returns: 0
large prime #1
9999999999007 Returns: 0
large prime #2
9999999999023 Returns: 0
large prime #3
9999999999049 Returns: 0
large prime #4
9999999999053 Returns: 0
large prime #5
9998250324001 Returns: 0
square of large prime #1
9998313564121 Returns: 0
square of large prime #2
9998503285681 Returns: 0
square of large prime #3
9998617119481 Returns: 0
square of large prime #4
9998667712489 Returns: 0
square of large prime #5
Submissions are judged against all 240 archived test cases, of which 17 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NumericalPerfectionLevel with a public method int getLevel(long long N) · 240 test cases · 2 s / 256 MB per case