Областная олимпиада по информатике. 9 класс. 2014-2015 учебный год.

Задача A. Факториал

Ограничение по времени:

2 секунды

Ограничение по памяти:

64 мегабайта

Условие этой задачи очень простое. Найдите наименьшее $K$ такое, что $K!$ делится на $N$ без остатка. $K! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (K-1) \cdot K.$

Формат входного файла

В первой и единственной строке дано число $N$ $(1 \le N \le 10^9).$

Формат выходного файла

Выведите ответ на задачу.

Примеры:

Вход

4

Ответ

4

Вход

8

Ответ

4

Замечание

$N \le 10 $ — $10\%$ тестов.
$N \le 100 $ — $20\%$ тестов.
$N \le 1000$ — $30\%$ тестов.
$N \le 10^6 $ — $40\%$ тестов.

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;
map <int , int> was , been;
bool chk() {
    for (map<int,int>::iterator it=was.begin() ; it!=was.end(); it++) {
        int x = it->second;
        int y = been[it->first];
        if (x > y) return true;
    }
    return false;
}
int main() {
    int n;
    cin >> n;
    for (int i=2; i*i<=n; i++) {
        while (n % i == 0) {
            was[i]++;
            n/=i;
        }
    }
    if (n != 1) was[n]++;
    int cnt = 0;
    while (chk()) {
        cnt++;
        int rep = cnt;
        for (int i=2; i*i<=rep; i++) {
            while (rep % i == 0) {
                been[i]++;
                rep/=i;
            }
        }
        if (rep != 1) been[rep]++;
    }
    
    cout <<cnt<<endl;
}