# Multipliers (codeforces)

This is the link to this algorithm topic: https://codeforces.com/problemset/problem/615/D

my code time limit exceeded on test40, I thought for a long time but no good way, is there a good optimization method, may be ?

mycode:

``````typedef long long ll;
ll mod = 1e9 + 7;

ll fast_mod(ll a, ll n, ll Mod)
{
ll ans=1;
a%=Mod;
while(n)
{
if(n&1) ans=(ans*a)%Mod;
a=(a*a)%Mod;
n>>=1;
}
return ans;
}

int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);     // IO

ll m;
cin >> m;
ll num = 1ll;
map<ll, ll> count;
for(int i = 0; i < m; i++)
{
ll p;
cin >> p;
count[p]++;
}

ll res = 1ll;
vector<ll> a;
vector<ll> b;
for(auto it = count.begin(); it != count.end(); it++)
{
a.push_back(it -> first);
b.push_back(it -> second);
}
for(int i = 0; i < a.size(); i++)
{
ll x = a[i];  // a kind of prime
ll y = b[i];  //  the count of the prime
ll tmp = fast_mod(x, y * (y + 1) / 2, mod);  // x^1 * x^2 * x^3 *...*x^y
for(int j = 0; j < b.size(); j++)  // calculate  ( tmp)^((b[0] + 1)*(b[1] + 1)*...*(b[b.size() - 1] + 1)), here b.size() is the number of different primes
tmp = fast_mod(tmp, i != j ? (b[j] + 1) : 1, mod) % mod;
res = (res * tmp % mod);
}

cout << res << endl;

return 0;
}

``````

Find the number of each different prime number, suppose x is one of the different prime number, then calculate x^1x^2x^y, y is the count of x, the result as tmp.Then the product of count of
other prime plus one as the exponent: (b[0] + 1)
(b[1] +1)(b[b.size() – 1] + 1), tmp as base.
The for loop divide the calculation into several steps.
Last, res * (tmp^ ((b[0] + 1)(b[1] +1)…*(b[b.size() – 1] + 1)))

## Solution

An other formula for the product of the divisors of `N` is `N ** (D/ 2)`, where D is the number of divisors and may be found from your map `count` by taking the product of `entry->second + 1` for every entry.

This does raise the question of what to do when `D` is odd, which it would be if `N` is a perfect square. In that case it is easy to compute `sqrt(N)` (the exponents would all be even, so you can halve them all and take the product of the primes to half of their original exponents), and then raise `sqrt(N)` to the power of `D`. Essentially this changes `N ** (D / 2)` into `(N ** (1 / 2)) ** D`.

For example if `N = 2 * 3 * 2 = 12` (one of the examples), then `D` will be `(2 + 1) * (1 + 1) = 6` and the product of divisors will be `12 ** (6 / 2) = 1728`.

Computing `N` (or its square root) should done modulo `mod`. Computing `D` should be done modulo `mod - 1` (the totient of `mod`, `mod` is a prime so its totient is just one less). `mod - 1` is even, so we could not have computed the modular multiplicative inverse of 2 to "divide" `D` by 2 that way. When `N` is a square then AFAIK we’re really stuck with computing its square root (that’s not so bad, but multiplying by a half would have been easier).

﻿﻿