Please explain the code of the tutoirla..i wanted to know about the term modulo inverse why we are using

#1

#include<bits/stdc++.h>
long long p = 1000000007;
using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
long long x;
cin >> x;

 vector<long long> vec;
 vec.resize(x);

 long long nOfDivisors = 1;

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

 long long ans = 1;


 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;
 }

 cout << ans << endl;
 //cin >> x;
 return 0;

}

#2

I am going to break down the code here.
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;
 }

Mod inverse is used when you are performing divisions under the modulo operation.

#3

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.

1 Like
#4

yeah i understood the concept