2

введите сюда описание изображения

#include <iostream>
using namespace std;
unsigned long long fact(int K)
{
    long long fact = 1;

    for (int i = K; i > 0; i--)
    {
        fact *= i;
    }

    return fact;
}
int main()
{
    int N = 4; // delitel
    long long i = 1;

    while (fact(i) % N != 0)
    {
        i++;
    }

    cout << i; // 4
    return 0;
}

При больших N ответ уже неверный. Что нужно изменить чтобы работало и при N <= 10^9 ?

6
  • Нужно использовать длинную арифметику. 15 дек 2016 в 10:13
  • @ВладимирМартьянов зачем?? Эта задача решается вообще не вычисляя факториала. тут основная сложность - разложить число на множители. "В лоб" - не успеет по времени. Поэтому нужно чуть умнее например двойным решетом.
    – pavel
    15 дек 2016 в 10:14
  • @pavel хочет факториал - что ж не помочь :-) 15 дек 2016 в 10:28
  • Хорошая задача, может гольф?
    – Cerbo
    15 дек 2016 в 11:11
  • Похоже, надо разложить N на простые делители, затем для максимального простого делителя посмотреть, по сколько раз в его факториал входят прочие простые делители - например, вот так, убирая соответствующие степени. Если все прочие делители убраны - значит, это и есть ответ. Если нет - то из оставшихся делителей надо как-то собрать минимальное число... но пока не знаю как - это комментарий, а не ответ :)
    – Harry
    15 дек 2016 в 14:41

3 ответа 3

2

Правильный способ:

  1. разложить число на простые множители (любой способ быстрее чем корень из N).

  2. перебираем все простые делители числа без повторений

  3. степень делители не превысит 64 (грубо говоря 2^64 > 10^18)

  4. степень числа x в факториале равна N/x + N/x^2 + N/x^3 + N/x^4 + N/x^5 дальше уже точно не понадобится...

  5. цикл по N/x от 1 и до степени числа. Вычислять ответ по формуле из 4 пока не превысит нужную степень вхождения.

  6. 5 пункт можно записать в формулу, но зачем

  7. берём максимум из того что вычислялось в пункте 5. Это и будет ответ.

    P.S. ответ для 1 - 0.

По просьбе - код. (факторизацию считаю сделанной ранее). Код написан без оптимизаций максимально показывая идею.

    int calcZ(int px, long long D){
        int res = 0;
        while (px){
            res+=px;
            px/=D;
        }   
        return res;
    }
    
    long long calc(map<long long,int> factor){
        long long ans = 0;
        for (auto x : factor){
            auto value = x.first;
            auto degree= x.second;
            int curD = 1;
            while (calcZ(curD,value) < degree)
                curD++;
            ans = max(ans,curD*value);
        }
        return ans;
    }

Запускаемый пример. http://ideone.com/OOqBlr

5
  • Что-то не очень понятно описано... Берем, скажем, 945 = 3*3*3*5*7. Пункт 2 - 3, 5, 7. Пункт 4 - 945/3+945/9+945/27=455. Пункт 5 - цикл по 945/3 = 309 от 1 и до... до степени 3? или до чего? Что значит цикл по N/x? Что вычислять? Какое значение? 2? 3? 1? Для 3 - это что? Словом, был бы крайне признателен или формальному описанию, или псевдокоду, или хотя бы разобранному примеру для того же 945...
    – Harry
    15 дек 2016 в 15:51
  • @Harry сделано)
    – pavel
    15 дек 2016 в 16:38
  • Я правильно понимаю, что для того же моего 945 я должен написать map<long long,int> m; m[3] = 3; m[5] = 1; m[7] = 1; cout << calc (m)<<endl; ? 3^3*5*7 = 945 - т.е. внести в map множители и степени?
    – Harry
    15 дек 2016 в 17:32
  • @Harry да, делать факторизацию можно любым способ, посчитал что копипастить смысла нет.
    – pavel
    15 дек 2016 в 17:46
  • В пункте 4 имеется в виду "степень простого числа x"
    – Cerbo
    15 дек 2016 в 19:29
1

Есть простой алгоритм. Число N нужно разложить на множетели и получить массив.

Теперь делаем цикл от 1 до N и каждое число раскладываем на множетели. Все найденые множетели очередного числа ищем в исходном массиве и если нашли - удаляем. Как только массив исходных множетелей стал пуст - приехали, нашли нужный К - им будет значение индекса.

4
  • Например, N - простое число порядка 10^9... не слишком ли много работенки? :)
    – Harry
    15 дек 2016 в 13:43
  • да, этот алгоритм будет работать хорошо только для n-гладких чисел, где n достаточно маленькое. Но я уже придумал другой алгоритм, который более быстрый.
    – KoVadim
    15 дек 2016 в 14:16
  • Колитесь :) Интересно посмотреть...
    – Harry
    15 дек 2016 в 14:22
  • Кстати, это задача для школьников. 10-11 класс...
    – Harry
    15 дек 2016 в 14:30
0

Это задача на алгоритмы, скорее. Не надо подходить к ней простым перебором. Тебе надо разложить число N на множители до простых чисел (подумать, что делать с повторяющимися (возможно перемножить)) и самое большое из получившихся чисел и будет искомой K.

2
  • перемножать точно не надо.
    – pavel
    15 дек 2016 в 10:21
  • @pavel Ну да, например, 512*13... :) Надо не перемножать, а хитро раскладывать...
    – Harry
    15 дек 2016 в 13:45

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.