Saiko~ No Contesuto #03 歯車と箱

問題

www.hackerrank.com

解法

明らかに上半分を掛け算する方に使って下半分を割り算に使ったほうが得になります。

ということで, この場合の分数の値を出力すればよいですが, C++ ではこれが面倒です。

これをやるためには, 下半分の掛け算と上半分の掛け算の最大公約数を求めなければなりませんが, これはそれぞれの数を素因数分解することによって得ることが出来ます。

const int MAXN = 100010;
const ll MOD = 1e9+7;
ll z[MAXN];

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

void calc(ll x, map<ll, int>& M) {
    for (ll i = 2; i*i <= x; i++) {
        int cnt = 0;
        while (x%i == 0) {
            x /= i;
            cnt++;
        }
        if (cnt) M[i] += cnt;
    }
    if (x > 1) M[x] += 1;
}

ll mod_pow(ll x, ll p) {
    if (p == 0) return 1;
    if (p == 1) return x;
    if (p%2) return (x*mod_pow(x, p-1)) % MOD;
    ll tmp = mod_pow(x, p/2);
    return (tmp*tmp)%MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> z[i];
    sort(z, z+N);
    ll child = 1, mother = 1, gcd = 1;
    for (int i = 0; i < N/2; i++) {
        (child *= z[i+N/2]) %= MOD;
        (mother *= z[i]) %= MOD;
    }
    map<ll, int> C, M;
    for (int i = 0; i < N/2; i++) {
        calc(z[i], C);
        calc(z[i+N/2], M);
    }
    for (int i = 2; i < MAXN; i++) {
        gcd *= mod_pow(i, min(M[i], C[i]));
        gcd %= MOD;
    }
    (child *= mod_inverse(gcd, MOD)) %= MOD;
    (mother *= mod_inverse(gcd, MOD)) %= MOD;
    cout << child << " " << mother << endl;
    return 0;
}