백준 1630

문제

오민식 성공

 

오민식을 만족하는 수: 1보다 크거나 같고, N보다 작거나 같은 모든 자연수로 나누어 떨어지는 수.

영식이와 다솜이는 N이 주어졌을 때, 오민식을 만족하는 가장 작은 수가 궁금해졌다. 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 주어진 입력에 대해 오민식을 만족하는 가장 작은 자연수를 987654321로 나눈 나머지를 출력한다.

풀이

1 부터 연속되는 증가하는 정수들의 곱셈에서 최소공배수가 생기는 규칙을 찾으면 문제가 풀린다.

모든 수는 1로 나누어 떨어지므로 1은 제외하고, 2부터 연속해서 나열해보면

2, 3, 2^2, 5, 2 * 3, 7, 2^3, 3^2 와 같이 나타낼 수 있다.

 

순서대로 곱해가면서 최소공배수를 확인하면 우선적으로

1.  lcm(a, b) = (a * b) % gcd(a, b) 이다. a, b가 서로소이면 gcd(a, b)는 1이고, a, b중 하나가 소수라면 항상 서로소이므로

a, b 둘중 하나가 소수라면 lcm(a, b) = a * b이다. 라는 것을 알 수 있다.

 

2. lcm(a, b) = (a * b) % gcd(a, b)를 다시 기억해서, 소수의 N승에 해당하는 자연수가 나오면 lcm 계산 과정에서 항상 gcd로 mod 연산을 해주었기 때문에 특정 소수의 N - 1승 까지만 최소공배수가 만족하고 있다는 사실 을 알수있다.

예를 들어, 1 부터 7 까지 곱했을때 이전에 계산 과정에 따라 2^2 * 3 * 5 * 7 이라는 것을 알 수 있다. 8은 2^3이고, lcm에서 2가 하나 부족하다는 것을 알 수 있다.

 

그러므로 두가지 조건을 만족하게 구현하면 된다.

 

#include <iostream>
#include <vector>
#define ll long long
using namespace std;
int isPrime[1000001], isTime[1000001];
vector<int>priArr;
void pcheck() {
    for(int i=2; i <= 1000000; i++) isPrime[i] = i;
    for(int i=2; i*i <=1000000; i++) {
        if(!isPrime[i]) continue;
        for(int j = i*i; j<=1000000; j += i) isPrime[j] = 0;
    }
    for(int i=2; i<=1000000; i++)
        if(isPrime[i]) priArr.push_back(i);
}
int main() {
    ll a = 1, N;
    cin>>N;
    pcheck();
    for(auto e : priArr) {
        long long check = e;
        while(check * e <= 1000000){
            check = check * e;
            isTime[check] = e;
        }
    }
    for(int i=1; i<=N; i++){
        if(isPrime[i])
            a = (a*i)%987654321;
        else {
            if(isTime[i])
                a = (a*isTime[i])%987654321;
        }
    }
    cout<<a;
}