VEGETA - Editorial

editorial
, ,
1

Problem Link - Majin Vegeta Practice Problem in 1400 to 1600 difficulty problems

Problem Statement:

Given an integer range [n, m] for each test case, the energy required to move between two consecutive levels n and n+1 is determined by the number of distinct prime factors of n. So, for each level n, we need to compute the number of distinct prime factors and sum them up for all levels between n and m inclusive.

Approach:

Prime Factorization:

  • The energy used to move from level n to n+1 is equal to the number of distinct prime factors of n. For example: For n = 6, the prime factors are {2, 3}, so the energy used is 2.

Sieve of Eratosthenes is typically used for finding primes, but here we will modify it to count the number of distinct prime factors for each number.

Precompute the number of distinct prime factors for all numbers up to 10^6:

  • Create an array prime_factors_count where prime_factors_count[i] holds the number of distinct prime factors of i.
  • Initialize the array as zero, then for each prime i, increment the count of prime factors for all multiples of i.

Sum the Distinct Prime Factors:

  • For each test case, simply sum the values in prime_factors_count from n to m.

Complexity:

  • Time Complexity: The modified Sieve of Eratosthenes runs in O(MAX log log MAX) time, which is efficient for MAX = 10^6. For each test case, we simply sum the values from prime_factors_count[n] to prime_factors_count[m], which takes O(m - n + 1) time. In the worst case, this is O(MAX) for a single test case.
  • Space Complexity: We use an array prime_factors_count of size MAX + 1, so the space complexity is O(MAX).