백준 1630 오민식 혼내주기

 

 

 

1 ~ 10까지의 수를 소인수분해하면 다음과 같다.

 

오민식을 만족하는 수는 오른쪽처럼 1부터 N까지의 수를 소인수분해하는 과정에서 각 소수의 최대 갯수이다.
에라토스테네스처럼 소수를 찾을 때 마다 소수가 최대 몇개 필요한지 찾아서 곱하면 된다.

 

 

 

(스포주의)
중간에 0이 나와서 계속 찍어봤는데, 987654321로 나누어지는 수가 있었다...(!!)
N이 1000000도 답이 0이어서 맞게 풀었나 몇번이나 찍어봤다.

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

const int MOD = 987654321;
bool visited[1000005];
int n;

void input() {
    cin >> n;
}

int main() {
    fastio;
    input();

    ll ans = 1;
    for(int i = 2; i <= n; ++i) {
        if(visited[i]) continue;
        int mx = 1;
        for(int j = i*2; j <= n; j +=i) {
            visited[j] = true;
            int t = j;
            int cnt = 0;
            while(t % i == 0 && t > 1) {
                t /= i;
                cnt++;
            }
            mx = max(mx, cnt);
        }
        while(mx--) {
            ans = (ans * i) % MOD;
        }
    }
    cout << ans;
}