백준 30169번: Primes and Multiplication

https://www.acmicpc.net/problem/30169

30169번: Primes and Multiplication

---

문제에서 나오는 $f(x,y)$와 $g(y,p)$의 정의를 잘 관찰해보면,

$$ \prod_{i=1}^{N} f(x,i) = \prod_{p|x} \left \{ \prod_{i=1}^{N} g(i,p) \right \} $$

이라는 걸 알 수 있습니다.

 

핵심은 여기서 괄호 속의

$$ \prod_{i=1}^{N} g(i,p) $$

인데, 이 값은 $g$의 정의에 의해 $N!$ 의 소인수분해에서 $p$ 가 몇 번 나타나는지를 의미하게 됩니다.

 

한편 이 문제에서 $x \leq 10^{9}$ 이므로, $O(\sqrt{x})$ 복잡도로 소인수분해 해도 충분히 시간 내로 들어옵니다.

 

그렇다면 어떻게 그 횟수를 구하냐는 게 다음 문제인데, 다행히 Legendre가 이미 밝혀놨고, 독자적으로 생각하기도 그나마 할 만 한 편입니다.

 

그대로 구현하면 정답이 나옵니다. 아래는 제 코드입니다.

#include <stdio.h>
#define mod 1000000007

long long Legendre_formula (long long N, long long P);

long long power_modular (long long X, long long Y);

int main() {
    
    int x;
    long long N;
    scanf("%d %lld", &x, &N);
    
    int prime_divisor[10];
    int count_prime_divisor = 0;
    
    if (x % 2 == 0) {
        prime_divisor[count_prime_divisor++] = 2;
        while (x % 2 == 0) {
            x /= 2;
        }
    }
    
    for (long long i = 3; i * i <= x; i += 2) {
        if (x % i == 0) {
            prime_divisor[count_prime_divisor++] = i;
            while(x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        prime_divisor[count_prime_divisor++] = x;
    }
    
    long long answer = 1;
    for (int i = 0; i < count_prime_divisor; i++) {
        answer = answer * power_modular(prime_divisor[i], Legendre_formula(N, prime_divisor[i])) % mod;
    }
    printf("%lld", answer);
    
    return 0;
}

long long Legendre_formula (long long N, long long P) {
    long long result = 0;
    N /= P;
    while (N) {
        result += N;
        N /= P;
    }
    return result;
}

long long power_modular (long long X, long long Y) {
    long long result = 1;
    while (Y) {
        if (Y % 2) {
            result = result * X % mod;
        }
        X = X * X % mod;
        Y /= 2;
    }
    return result;
}​

(C11, 0ms, 1116KB, 제출번호 67350807)

---

이 문제는 Codeforces Round #589 (Div.2) 에 C번으로 출제된 문제로, 에디토리얼에 따르면 전체 시간 복잡도는 $O(\sqrt{x} + \log \log x \times \log N)$ 입니다.

 

여기서 $\log \log x$는 사실 부정확한게, https://math.stackexchange.com/questions/2051208/asymptotic-behaviour-of-omegan와 같은 게시글을 보면 사실 $O(\sqrt{x} + \frac{\log x}{\log \log x} \times \log N)$를 써야 합니다.