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