Non-Faktorisasi

Soal#

Informasi#

• Sumber: CompFest 7 - Final CPC Junior

Arsip#

• TLX

Ringkasan#

Definisikan $M = A_1 \cdot A_2 \cdot \ldots \cdot A_N$. Tentukan banyak bilangan yang lebih kecil atau sama dengan $M$ dan koprima dengan $M$. Dua buah bilangan $A$ dan $B$ dikatakan koprima jika dan hanya jika FPB (faktor persekutuan terbesar) $A$ dan $B$ adalah $1$.

Solusi#

Petunjuk#

Pembahasan#

Soal ini terbagi menjadi tiga subsoal. Subsoal pertama dapat dengan mudah diselesaikan dengan cara mengecek kondisi $gcd(i, M) = 1$ untuk setiap $i$ di antara $1$ sampai dengan $M$ (inklusif). Solusi ini berjalan dalam waktu $O(M \log {M})$.

Untuk menyelesaikan subsoal kedua dan ketiga, kita membutuhkan solusi yang lebih efisien. Kita bisa menggunakan Euler's totient function yang dilambangkan dengan huruf Yunani $\varphi$ atau $\phi$. Jawaban dari soal ini adalah nilai dari $\varphi(M)$.

Misal $p_1, p_2, ..., p_k$ adalah faktor-faktor prima dari $M$. Fungsi tersebut didefinisikan sebagai $$\varphi(M) = M \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_k}\right)$$

Mencari semua faktor prima dari $M$ dapat dilakukan dengan kompleksitas waktu $O(\sqrt{M})$. Ini sudah cukup untuk menyelesaikan subsoal kedua, namun tidak bisa digunakan untuk subsoal ketiga. Untuk meyelesaikan subsoal ketiga, kita bisa memanfaatkan sifat fungsi $\varphi$, yaitu fungsi $\varphi$ adalah multiplicative function. Dengan kata lain, untuk dua bilangan $a$ dan $b$ yang saling koprima, berlaku $$\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)$$

Untuk memudahkan, berikut adalah faktorisasi prima dari $M$. $$M = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k}$$

Jadi $$\begin{aligned} \varphi(M) &= \varphi(p_1^{e_1}) \cdot \varphi(p_2^{e_2}) \cdot \ldots \cdot \varphi(p_k^{e_k}) \\ &= p_1^{e_1}\left(1 - \frac{1}{p_1}\right) \cdot p_2^{e_2}\left(1 - \frac{1}{p_2}\right) \cdot \ldots \cdot p_k^{e_k}\left(1 - \frac{1}{p_k}\right) \\ &= p_1^{e_1}\left(\frac{p_1 - 1}{p_1}\right) \cdot p_2^{e_2}\left(\frac{p_2 - 1}{p_2}\right) \cdot \ldots \cdot p_k^{e_k}\left(\frac{p_k - 1}{p_k}\right) \\ &= p_1^{e_1 - 1}(p_1 - 1) \cdot p_2^{e_2 - 1}(p_2 - 1) \cdot \ldots \cdot p_k^{e_k - 1}(p_k - 1) \end{aligned}$$

Karena masukan yang diberikan adalah $A_1, A_2, \ldots, A_N$, maka kita dapat melakukan faktorisasi prima pada $A_i$ ($1 \le i \le N$) dan menjumlahkan eksponen untuk setiap faktor prima.

Kode#

#include <iostream>
#include <map>
using namespace std;
typedef long long int lli;

const int MOD = 1E9 + 7;

int N, Ai;
map <int, int> powers;

int Pow(lli x, int y){
    lli ret = 1;
    while(y){
        if(y & 1) (ret *= x) %= MOD;
        (x *= x) %= MOD;
        y >>= 1;
    }
    return ret;
}

int main(){
    cin >> N;

    while(N--){
        cin >> Ai;
        for(int i = 2; i * i <= Ai; i++){
            while(Ai % i == 0){
                Ai /= i;
                powers[i]++;
            }
        }
        if(Ai != 1) powers[Ai]++;
    }

    lli ans = 1;
    for(const auto& p : powers){
        (ans *= p.first - 1) %= MOD;
        ans *= Pow(p.first, p.second - 1);
        ans %= MOD;
    }

    cout << ans << '\n';
    return 0;
}