Getting only 17 points

#1

I am getting only 17 points ,my code is only passing the 1st TC.

Here is my logic-
-first i am generating n by multiplying all the primes given.
ex: 2^1 * 3^1 * 5^1 = 30

  • now i am generating all the divisors of 30 that are 1,2,3,5,6,10,15,30.

-now i am multiplying all these to generate our number p = 810000

-now i am finding its number of divisors which is the answer.

What am i doing wrong? and what should i do to completely solve this problem?

#2

hello @rohitmathur.mathur.6

The product of all the divisors of a number N is N^(x/2) where x is the number of divisors of N. The number of divisors is given by product of prime powers+1 for N.

so simply u have to compute all divisors of N^(x/2)

#3

I am still not getting AC, can you please tell me why?
This is my code - https://ideone.com/TlQ0xb

#4

the result will be changed because of modulo.

dont implement it like this.

check this->

This portion calculates the number of divisors of given number
long long nOfDivisors = 1;

 for (long long i = 0; i<x; i++)
 {
      cin >> vec[i];
      nOfDivisors = (nOfDivisors*(vec[i] + 1)) % p;
 }

The product of all the divisors of a number N is N^(x/2) where x is the number of divisors of N. The number of divisors is given by product of prime powers+1 for N.

Now the next part is basic P&C.

 for (long long i = 0; i<x; i++)
 {
      vec[i] = (nOfDivisors*vec[i])%p;
      vec[i] = (vec[i]*500000004)%p; // 500000004 is mod_inv(2,1000000007);
      ans = (ans*(vec[i] + 1)) % p;
 }
#5

Can you please explain this part -
for (long long i = 0; i<x; i++)

{

  vec[i] = (nOfDivisors*vec[i])%p;

  vec[i] = (vec[i]*500000004)%p; // 500000004 is mod_inv(2,1000000007);

  ans = (ans*(vec[i] + 1)) % p;

}

can you explain why we are doing nOfDivisors*vec[i], and also vec[i]*500000004 ?

#6

se if vec[i] is power if N. then in N^X/2 it will be
vec[i]*N^x/2 right?

[quote=“rohitmathur.mathur.6, post:5, topic:157287”]
vec[i] = (nOfDivisors*vec[i])%p;

these two lines is for the same. see becuase we are dealing with mod we cant divide direcly by 2 , wwe have to take mod inverse of 2 and then mulitly it.
second line is for the same

vec[i] is now hold power of ith prime in N^X/2 so its contribution in factors will be vec[i]+1