link of question
http://codeforces.com/contest/615/problem/D link of solution is http://codeforces.com/contest/615/submission/15260890
In below code i am not able to understand why 1 is subtracted from mod where mod=1000000007
ll d = 1;
ll ans = 1;
for (auto x : cnt) {
ll cnt = x.se;
ll p = x.fi;
ll fp = binPow(p, (cnt + 1) * cnt / 2, MOD);
ans = binPow(ans, (cnt + 1), MOD) * binPow(fp, d, MOD) % MOD;
d = d * (x.se + 1) % (MOD - 1);//why ??
}
Apart from the fact that there is the code does not make much sense as out of context as it is, there is the little theorem of Fermat:
Whenever MOD is a prime number, as 10^9+7 is, one can reduce exponents by multiples of (MOD-1) as for any a not a multiple of MOD
a ^ (MOD-1) == 1 mod MOD.
Which means that
a^b == a ^ (b mod (MOD-1)) mod MOD.
As to the code, which is efficient for its task, consider n=m*p^e where m is composed of primes smaller than p.
Then for each factor f of m there are factors 1*f, p*f, p^2*f,...,p^e*f of n. The product over all factors of n thus is the product over
p^(0+1+2+...+e) * f^(e+1) = p^( e*(e+1)/2 ) * f^(e+1)
over all factors f of m. Putting the numbers of factors as d and the product of factors of m as ans results in the combined formula
ans = ans^( e+1 ) * p^( d*e*(e+1)/2 )
d = d*(e+1)
which can now be recursively applied to the list of prime factors and their multiplicities.