Non-Faktorisasi

Problem#

Information#

• Source: CompFest 7 - Final CPC Junior

Archive#

• TLX

Summary#

Define $M = A_1 \cdot A_2 \cdot \ldots \cdot A_N$. Count how many integers are less than or equal to $M$ and coprime with $M$. Two integers $A$ and $B$ are said to be coprime if and only if the greatest common divisor between $A$ and $B$ is $1$.

Solution#

Hint#

Explanation#

This problem is divided into three subtasks. First subtask can be solved easily by checking if $gcd(i, M) = 1$ for each $i$ from $1$ to $M$. This solution runs in $O(M \log {M})$ time.

To solve the second and third subtasks more efficiently, we can use Euler's totient function, denoted by the Greek letter $\varphi$ or $\phi$. The answer to this problem is $\varphi(M)$. Let $p_1, p_2, ..., p_k$ be the prime factors of $M$. This function is defined as: $$\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)$$

Finding all prime factors of $M$ can be done with a time complexity of $O(\sqrt{M})$. This is sufficient to solve the second subtask but cannot be used for the third subtask. To solve the third subtask, we can use the property of $\varphi$, which states that $\varphi$ is a multiplicative function. In other words, for two integers $a$ and $b$ that are coprime with each other, the following applies: $$\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)$$

For easier computation, we first factorize $M$. Here is the prime factorization of $M$: $$M = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k}$$

So, $$\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}$$

Given the inputs $A_1, A_2, \ldots, A_N$, we can factorize $A_i$ ($1 \le i \le N$) and sum the exponents for each prime factor of $M$.

Code#

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