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

Есеп A. Факториал

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

2 секунды

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

64 мегабайта

Бұл есептiң берiлгенi өте оңай. $K!$ қалдықсыз $N$-ға бөлiнетiн ең кiшкентай сан табыңыз. $K! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (K-1) \cdot K.$

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

Берiлгеннiң бiрiншi жолында бiр ғана сан $N$ $(1 \le N \le 10^9)$ берiлген.

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

Бiр ғана сан — есептiң жауабын шығарыңыз.

Примеры:

Вход

4

Ответ

4

Вход

8

Ответ

4

Замечание

$N \le 10$ — $10\%$ тест үшiн.
$N \le 100$ — $20\%$ тест үшiн.
$N \le 1000$ — $30\%$ тест үшiн.
$N \le 10^6$ — $40\%$ тест үшiн.

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

кодты корсету/жасыру

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

C++

Copy