Help me identify the error in my code/logic

#1

For this problem, I thought my logic like this:
let the number whose prime factorization is given in the array be x, then x=a1^(arr[1])a2^(arr[2])a3^(arr[3])… So, if all the divisors of x are multiplied I am calculating the freq of occuring of each of these primes (a1,a2,…) in that product. We can say a1 must have occured say denote it by temp= (arr[2]+1)(arr[3]+1)… So, each power of a1 from [1,arr[1]] must have occured temp times in that product. The total contribution of a1 in the final product will be temp(arr[1])(arr[1]+1)/2. Similarly we can calculate for other primes. And since answer will be in modulo field, so instead of dividing, I am multiplying modulo multiplicative inverse.

Is there anything wrong with my code/logic?

#2

Hi @ankitsinghix05,

You don’t need to compute sieve for this.

#3

Hi @PUNEET_GOEL, Is my logic right and what about my code ? And If my logic/code is wrong, explain your code.

#4

Hi @ankitsinghix05,

temp=((q%mod)(num%mod)((num+1)%mod)*((fast_modulo_power(2,mod-2,mod)))%mod)%mod;

Change this line to,

temp = (num*(num+1))%mod;
temp = (temp*q)%mod;
temp = (temp*fast_modulo_power(2,mod-2,mod))%mod;
1 Like
#5

Hi @PUNEET_GOEL, this modification worked. Also can you share the logic of your code?

#6

Hi @ankitsinghix05,
My logic is similar to yours. It is just more optimized.

  1. You don’t need to compute sieve.
  2. x = (a[i] * (a[i]+1))/2
    q = productOfAllElements / (a[i] + 1)
    Now, we need to add (q * x) to the ans,
    q * x = (a[i] * productOfAllElements) / 2
#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.