HackerRank Ad Infinitum 13 - Math Programming Contest

general
,
1

Probleam Here

I was trying to solve this problem and I am not able to pass the test cases please help me.

My approach for this problem:

1.Number N get the frequency of all prime factors [a:i, b:j, c:k…..] where a,b,c.. is prime factor of N and i,j,k.. are frequencies of a,b,c.. respectively  

2.Now sum of all factor of N will be [a^0+a^1+…a^i]*[b^0+b^1…a^j]*[c^0+c^1+..c^k]

To solve this problem I took two array nFact[] and nFactP[]

nFact[] Holds frequencies of each prime factor of any number on its index(like count sort)

nFactP[] Holds the sum of powers of any number on its index like for example 3 is index and nFact[A] holds 2 then nFactP[A] will hold [3^0+3^1+3^2]

Now when a number X is multiplied to N then do prime factorization of X

if F is a factor of X then update these:

   1.ans=ans/nFactP[F] (clear the previous value of nFactP[F] from the answer)

   2.nFact[F]=nFact[F]+1 (Add 1 to frequency of F)

   3.nFactP[F]=nFactP[F]+(F^nFact[F]) (Add one more power of F (Highest Power))

   4.asn=ans*nFactP[F]

Print ans for given X

Is there anything wrong with my logic or I implemented it wrong ?

Brute Force Here

Solution Here

2

I found something in your implementation (might be considered wrong in point 1) in your algo too, but it’s not obvious).

You must not use integer division for for dividing in modular arithmetic. The correct implementation of “division” in this case is multiplication with the modular inverse:

x/y \operatorname{mod} p := x* y^{-1} \operatorname{mod} p

which can be computed either with the extended euclidean algorithm or by using the identity

y^{-1}=y^{p-2} \operatorname{mod} p
3

There are a few things that seem wrong to me,

  1. (a/b)%MOD != (a%MOD)/(b%MOD) // take the inverse module here instead.
  2. Also take care of negative values while doing a modulo , say // if(nFactP[i]<0)nFactP[i]+=MOD;//same for all
  3. Also assign all your arrays as long long int.

Rest the logic seems fine ,but why add 1 to nFact[F] and keep updating the ans?? If F was factor of previous n just take the module inverse of the ans due to previous nFact[F] and after calculating power of F in x, Do it once !

4

OK admit that is a bug but I also try to do it in python without any modular arithmetic and I was printing only (ans mod p) and guess what that was also wrong answer even for small integers.

5

I don’t get what you are trying to say in last two lines :frowning:

6

I was telling you an optimisation as you were using power function at each occurrence of a factor F of x, so an extra O(log(n)) at each step. But never mind, i ran your code, No issue of time limit. :smiley: