Fetus86_and_Luki49's blog

Help Needed in TOPH Problem.
By Fetus86_and_Luki49, history, 4 years ago, In English

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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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}$$$)

→ Reply