LIFE_GOES_ON's blog

By LIFE_GOES_ON, history, 5 weeks ago, In English,

In this 615D - Multipliers after analyzing some cases, I saw that,

If a number n = p1^a * p2^b * p3^c.

Then for the answer, the contribution of each prime is something like -

Let that , calculating the contribution of p1 --->

x = (a * (a+1) )/2;
y = (b+1)*(c+1) [ That is , how many divisors are there without the prime p1]

z = x*y
so the contribution of p1 is  p1^z

To calculate y , I had to use two loops. And got TLE 86303876 . How to optimize this portion?

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by LIFE_GOES_ON (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by LIFE_GOES_ON (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Product of all divisors can be calculated by : If n has divisor a1 then it also has n/a1 Hence all above such pair unite to n in product. Hence total such pair would be number of factors/2 just keep corner case of odd divisor.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Right now your method is O(n^2*log(n)) at worst. Your method can work just fine if you precompute the total number of divisors % p-1 = q. Say phi() is euler's totient function. Let's say you want the contribution of prime p1, then the contribution z = x*y = x*q/(a+1) = x*q*(a+1)**(phi(p-1)-1) % (p-1). The reason this is true is because the modular inverse of a number b mod p-1 is (b**(phi(p-1)-1)) % p-1. Then the problem can be solved in O(n*log(n)) time. You can calculate euler's totient function in O((p-1)^0.5) time.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what have you meant by ( ** ) ?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it is used for something raised to the power (2**10 =1024)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But for this (a+1) and (p-1) have to be relatively prime. Here p is already a prime so (p-1) will be even . And again 'a' can be either odd or prime. So are you sure about your solution ? Or I am missing something .