WA and TLE in Playing With Divisors is Fun

#1

ques:
https://hack.codingblocks.com/contests/c/547/941
code:
https://ide.codingblocks.com/s/57501

#2

Please Explain your logic.
You have yo calculate for every prime factor of n, the power that will be present in prime factorisation of P. Then product of it will be the answer.

#3

solution code https://ide.codingblocks.com/s/57522

#4

multiply prime[i]^a[i] to get the number.
Then find product of all of its divisors and then finding number of divisors of the product

#5

I think I am taking extra mods, can u pls check where r they not required?

#6

to be frank, I don’t understand a line in your code :sweat_smile:
I gotta repair my own code :disappointed_relieved:

#7

ll n,i,s=1;
cin>>n;
vector v(n);
for(i=0;i<n;i++)
{
cin>>v[i];
v[i]++;
v[i]=v[i]%Mod;
s=(s*(v[i]))%Mod;

}
ll cou=1;
for(i=0;i<n;i=i+1)
{
    ll q=modInverse(v[i],Mod);
    ll t=(s*q)%Mod;
    
    ll p=((v[i]-1+Mod)%Mod*v[i])%Mod;
    p=(p*modInverse(2,Mod))%Mod;
    t=(t*p)%Mod;
   // trace(t);
    t=(t+1)%Mod;
   
    cou=(cou*t)%Mod;
}
cout<<cou<<"\n";
return 0;
#8

above is the main logic of the code,

#9

I’ll explain my logic :

s is total number of divisors number N.

in for loop for each ‘i’ i’m calculating number of divisors that can be formed using all powers of ‘i’ , (those will be divisors of P )

to do calculate first ‘t’ t= number of divisors of ‘N’ containg i.
t=s/v[i].

number of different powers of i will be 1,2 ,3 4…till v[i].

total sum of this will be p=(v[i]-1)v[i]/2; (n(n+1)/2 sum of n terms, we have incremented v[i] inititally so fomula is bit changed put v[i]-1 in place of n )

multiply p and t and increment it and take product of it for all values of i.

Hit Like if you get it.

I know logic is very different it’s , mathematical, you can contact me personally if you still don’t get it.