乘数（codeforces）

Question

这是此算法主题的link：https://codeforces.com/problemset/problem/615/D

我的代码在test40上超限，想了很久也没有什么好的办法，有没有好的优化方法，可以吗？

我的代码：

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

求出每个不同素数的个数，假设x是其中一个不同素数，则计算x^1x^2... x^y，y是x的个数，结果为tmp.Then个个数的乘积其他质数加一作为指数：(b[0] + 1)(b[1] +1)...(b[b.size () - 1] + 1), tmp 作为基础。 for 循环将计算分为几个步骤。最后，res * (tmp^ ((b[0] + 1)(b[1] +1)...*(b[b.size() - 1 ] + 1)))

Answer 1

N 的除数乘积的另一个公式是 N ** (D/ 2)，其中 D 是除数的数量，可以从地图 count 中找到乘积每个条目的 entry->second + 1。

这确实提出了当 D 是奇数时该怎么做的问题，如果 N 是一个完全正方形。在那种情况下，计算 sqrt(N) 很容易（指数都是偶数，因此您可以将它们全部减半并将素数的乘积减为原始指数的一半），然后提高 sqrt(N)的 D 次方。从本质上讲，这会将 N ** (D / 2) 更改为 (N ** (1 / 2)) ** D.

例如，如果 N = 2 * 3 * 2 = 12（示例之一），则 D 将为 (2 + 1) * (1 + 1) = 6，除数的乘积将为 12 ** (6 / 2) = 1728.

计算 N（或其平方根）应该以 mod 为模完成。计算 D 应该对 mod - 1 取模（mod、mod 的 totient 是质数，所以它的 totient 只少一个）。 mod - 1 是偶数，所以我们无法通过这种方式计算 2 的模乘逆来“除以”D。当 N 是一个正方形时，据我所知，我们真的很难计算它的平方根（这还不错，但乘以一半会更容易）。

乘数（codeforces）

Multipliers (codeforces)

algorithm

number-theory