PROBLEM LINK:Author: Hitesh Ramchandani Tester: Sagar Gupta Editorialist: Hitesh Ramchandani DIFFICULTY:SIMPLEEASY PREREQUISITES:Math, Sieveoferatosthenes PROBLEM:A good number is a number whose count of divisors is greater than the count of divisors for all the numbers less than it. You have to find number of good numbers between two integers L and R(inclusive). QUICK EXPLANATION:These good numbers are called highly composite numbers. Let N = 2^a2 * 3^a3 * 5^a5 ... p^ap (ie prime factorization of N ). A number N is a good number if :
EXPLANATION:Naive approach(Subtask #1 30 pts): Calculate all divisors of a number and store it which takes O(summation over i from 1 to n root(i)). This is sufficient for 30 points and will fail for larger test cases. Subtask #2(70 pts): To answer the problem, we need to compute if a number N is good or not (or in other words highly composite). For this we need to calculate prime factorization of N. To calculate Prime factorization of N efficiently, we use Sieveoferatosthenes which calculates prime numbers from 1 to N in O(Nlog^2(n)). So we first precompute all the prime numbers upto 10^7 using Sieveoferatosthenes. Now for every N, we check if it satisfies the above conditions and also keep a count of number of divisors using the formula : num of divisors = (a2+1)(a3+1)*(a4+1)...(ap+1). Now consider N = 30 (2.3.5), it satisfies the above conditions but is still not a good number because N = 24 (2^3*3) also has 8 divisors. So it is necessary to store this information that number of divisors of 24 is 8 and thus even though 30 satisfies the above conditions, it is not a good number. Precompute and store if N is good or not for all N's from 1 to 10^7. TIME COMPLEXITY:O(N*log^2(N)) ALTERNATIVE APPROACH:The number of good numbers upto 10^7 is just 48. One can hardcode those numbers and solve the problem. TIME COMPLEXITY:O(1)
This question is marked "community wiki".
asked 12 Dec '16, 16:37
