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^2...x^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).