Codeforces Round #338 Multipliers

問題概要
とても大きな数nがある。
nの素因数が与えられるので、nの約数の総積をmod 1000000007で求めよ。

制約
nの素因数の個数 <= 200,000
2 <= nの素因数 <= 200,000

解き方
数論の知識が必要。

1. d(x)をxの約数の個数とすると、gcd(a, b) = 1のとき、d(ab) = d(a) d(b)となる。
2. nの約数の総積は、n^(d(n)/2)となる。
3. gcd(a, n) = 1のとき、a^x = a^(x % (n-1)) (mod n)となる。

1. はdivisor関数はmultiplicativeという有名な話。因数分解された数の約数の個数を高速に数える方法を理解していれば確かにそうだと分かる。

2. は最近知った。これは、約数を昇順に列挙したものと、降順に列挙したものを上下に並べて、上下の積を取ればそうなることが分かる。

3. は知らなかった。modで計算するとき冪乗の右肩の数は%取っていけないのは知っていたけど、mod nのときは% (n-1)を計算すればいいらしい。これはフェルマーの小定理から導ける。

サンプル解
上の3つを組み合わせて解く。詳しい式変形はeditorial参照。

#include <iostream>
#include <map>

using namespace std;

const long long MOD = 1e9 + 7;

long long mpow(long long x, long long p, long long mod) {
  long long ret = 1;
  while (p) {
    if (p & 1)
      ret = ret * x % mod;
    x = x * x % mod;
    p >>= 1;
  }
  return ret;
}

int main(int argc, char *argv[])
{
  int m;
  cin >> m;
  map<long long, int> p;

  for (int i = 0; i < m; i++) {
    long long x;
    cin >> x;
    ++p[x];
  }

  long long ret = 1;
  long long d = 1;
  for (const auto& pr : p) {
    long long x = pr.first;
    long long k = pr.second;

    long long f = mpow(x, k*(k+1)/2, MOD);
    ret = mpow(ret, k+1, MOD) * mpow(f, d, MOD) % MOD;
    d = d * (k+1) % (MOD-1);
  }
  
  cout << ret << endl;
  
  return 0;
}