Блог пользователя Fetus86_and_Luki49

Автор Fetus86_and_Luki49, история, 4 года назад, По-английски

How Can I solve this problem!https://toph.co/p/crypto-number Will be grateful if anyone can help. Thank You. TLE-O(q*sqrt(k)) time.

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

It's really a nice Number Theory problem.

In the problem statement you can note that r, p -both greater than 1 from it you can conclude the following:

  • When we factor the number of prime factors, you can note that the lowest exponent of these factors is 2.
  • Above the cube root of the number, there is one prime factor and the exponent of this factor is 2 or that there are no factors above the cube root.

From the previous observations, you can find the factors which are less than or equal the cube root in for-loop then you can check if there is a prime factor above the cube root or not.

In this way you can calculate prime factors for K with time complexity O($$$\sqrt[3]{K}$$$) then from the prime factors, you can find the divisors, and then the answer will be the frequency of the divisors in Array C.

AC solution

The Time Complexity O($$$Q\times\sqrt[3]{K}$$$)