06.10.2016 10:24
ia_bobrova 46 8100 Источник
Всем доброго времени суток! 30 сентября закончился прием заявок в школу программирования HeadHunter 2016. В этой статье я хотела бы разобрать задачи заочного этапа. Надеюсь, что моя статья будет полезной, учитывая, что при решении задач пришлось посетить не один десяток сайтов. Я имею небольшой опыт в программировании, поэтому я не утверждаю, что мое решение единственно верное. Всегда буду рада услышать Вашу критику!
При решении задач используется язык программирования Java.

Статья исправлена с помощью комментариев пользователей: используется один цикл в решении первой задачи, при вычислении факториала натурального числа используется тип BigInteger вместо long, исправлена вторая задача.

Задача 1


Дано равенство, в котором цифры заменены на буквы: rqr + rqq = sqr. Найдите сколько у него решений, если различным буквам соответствуют различные цифры (ведущих нулей в числе не бывает).

Для решения этой задачи можно выбрать два пути: решить ее «в лоб» с использованием трех вложенных циклов for или преобразовать выражение и использовать только два вложенных цикла for.

Выберем второй путь. Буквы в выражении условия задачи являются цифрами, а это значит, что каждое из них изменяется в пределах от 0 до 9. Теперь вспомним представление цисла в десятичной системе счисления и преобразуем выражение к следующему виду: s = 2r + 0.11q. Тогда код решения задачи будет выглядеть следующим образом:
Старое решение
public class FirstTask {
    public static void main(String[] args){
        int count = 0;
        for (int q = 0; q < 10; q++){
            for (int r = 1; r < 10; r++){
                if ((r != q)){
                    double s = 2 * r + 0.11 * q;
                    if (s % 1 == 0 && s != 0 && s < 10) 
                       count++;
                }
            }
        }
        System.out.println("count is " + count);
    }
}


В условии задачи указано, что не должно быть ведущих нулей, исходя из этого были выбраны начальные значения для переменных. Для переменной s необходимо использовать тип double для корректного выполнения условия s % 1 == 0. Данная программа считает следующие тождества:
101 + 100 = 201.0
202 + 200 = 402.0
303 + 300 = 603.0
404 + 400 = 804.0
count is 4

Если учесть, что q = 0, то имеем только один цикл:
public class FirstTask {
    public static void main(String[] args){
        int count = 0;
        for (int r = 1; 2 * r < 10; r++)
        count++;
        System.out.println("count is " + count);
    }
}

Задача 2


Наименьшее число m, такое, что m! делится без остатка на 10 — это m=5 (5! = 120). Аналогично, наименьшее число m, такое, что m! делится без остатка на 25 — это m=10. В общем случае, значение функции s(n) равно наименьшему числу m, такому что m! без остатка делится на n.
Определим функцию S(M, N) = ?s(n) для всех n ? [M, N]. К примеру, S(6, 10) = 3 + 7 + 4 + 6 + 5 = 25. Найдите S(2300000, 2400000).

Разобьем задачу на несколько этапов. Нам необходимо построить метод, вычисляющий факториал натурального числа (метод factorial(BigInteger m)), вычисляющий значение m, удовлетворяющее условию задачи (метод mod(BigInteger n)) и метод, вычисляющий значение функции S(M, N) (метод solve(BigInteger n, BigInteger m)).

Обратите внимание, что в условии задачи необходимо найти значение функции S(2300000, 2400000), факториал от аргументов которой будет большим числом, поэтому для всех числовых переменных используем тип BigInteger (иначе вычисления будут некорректными).

Метод factorial(BigInteger m) реализуем с помощью цикла: текущую переменную ret умножаем на переменную цикла for и затем присваиваем ей результат, пока не будут выполнены все итерации цикла.
Метод mod(BigInteger n) выполняет поиск наименьшего значения m, которое удовлетворяет условию задачи: factorial(m) % n == 0. Для подбора таких значений используем цикл for. Как только такое m нашлось, выходим из цикла.

Метод solve(BigInteger n, BigInteger m) вычисляет сумму всех значений, полученных с помощью метода mod(BigInteger n) с помощью цикла for, переменная которого изменяется от n до m с шагом в единицу.
Старое решение с использованием BigInteger
public class SecondTask {
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger n = BigInteger.valueOf(Integer.parseInt(br.readLine()));
        BigInteger m = BigInteger.valueOf(Integer.parseInt(br.readLine()));
        solve(n,m);
    }
    public static BigInteger factorial(BigInteger n) {
        BigInteger res = BigInteger.ONE;
        if (n.intValue() == 0 || n.intValue() == 1) return res;
        else {
            for (BigInteger i = BigInteger.ONE; i.compareTo(n) <= 0; i = i.add(BigInteger.ONE)) {
                res = res.multiply(i);
            }
        }
        return res;
    }
    public static BigInteger s(BigInteger n) {
        BigInteger res = BigInteger.ZERO;
        for (BigInteger m = BigInteger.ZERO; m.compareTo(n) <= 0; m = m.add(BigInteger.ONE)) {
            System.out.println("m = " + m);
            if ((factorial(m)).mod(n).equals(BigInteger.ZERO)) {
                res = m;
                break;
            }
        }
        return res;
    }
    public static BigInteger solve(BigInteger N, BigInteger M){
        BigInteger res = BigInteger.ZERO;
        for (BigInteger i = N; i.compareTo(M) <= 0; i = i.add(BigInteger.ONE)){
            BigInteger m = s(i);
            res = res.add(m);
        }
        return res;
    }

Тестируем программу для примера в условии задачи S(6, 10):
6
10
25

Результат выполнения программы для S(2300000, 2400000) (был использован тип long:
2300000
2400000
6596625


Решение этой задачи использует алгоритм в комментарии.
public class SecondTask {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        Date startSolve = new Date();
        solve(n, m);
        Date finishSolve = new Date();
        long solveTime = finishSolve.getTime() - startSolve.getTime();
        System.out.println("solveTime is " + solveTime + " ms");
    }
    public static int s(int n) {
        TreeMap<Integer, Integer> treemap = new TreeMap<Integer, Integer>();
        int i = 2, count = 1;
        while (i <= n){
            if (n % i == 0){
                if (treemap.containsKey(i)){
                    count++;
                    treemap.put(i, count);
                } else {
                    count = 1;
                    treemap.put(i, count);
                }
                n = n / i;
                i--;
            } i++;
        }
        int p = treemap.lastKey(), k = treemap.get(treemap.lastKey()), m = 0;
        if (k > p){
            do k--;
            while(k > p);
            m = k * p;
        } else m = k * p;
        return m;
    }
    public static int solve(int n, int m){
        int res = 0;
        for (int i = n; i <= m; i++)
            res += s(i);
        System.out.println(res);
        return res;
    }
}

Тестируем программу для примера в условии задачи S(6, 10):
6
10
25
solveTime is 0 ms

Результат выполнения программы для S(2300000, 2400000):
2300000
2400000
1796256390
solveTime is 130854 ms

Задача 3


Рассмотрим все возможные числа ab для 1<a<6 и 1<b<6:
22=4, 23=8, 24=16, 25=32 32=9, 33=27, 34=81, 35=243 42=16, 43=64, 44=256, 45=1024, 52=25, 53=125, 54=625, 55=3125. Если убрать повторения, то получим 15 различных чисел. Сколько различных чисел ab для 2<a<135 и 2<b<136?

Для возведения числа в степень используем метод Math.pow(x,y) (зачем изобретать велосипед?). Правда, при использовании этого метода необходимо, чтобы все числовые переменные имели тип double.

Решаем задачу с помощью двух коллекций: ArrayList используем для добавления элементов ab, HashSet используем для удаления из коллекции всех повторяющихся элементов.
public class ThirdTask {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("type the interval for a");
        double a1 = Long.parseLong(br.readLine());
        double a2 = Long.parseLong(br.readLine());
        System.out.println("type the interval for b");
        double b1 = Long.parseLong(br.readLine());
        double b2 = Long.parseLong(br.readLine());
        pow(a1, a2, b1, b2);
    }
    public static ArrayList<Double> pow(double a1, double a2, double b1, double b2){
        ArrayList<Double> arr = new ArrayList<>();
        for (double i = a1 + 1; i < a2; i++){
            for (double j = b1 + 1; j < b2; j++){
                arr.add(Math.pow(i,j));
            }
        }
        System.out.println("arr size is " + arr.size());
        HashSet<Double> list = new HashSet<Double>(arr);
        System.out.println("now arr size is " + list.size());
        return arr;
    }
}

Тестируем программу для 1<a<6 и 1<b<6:
type the interval for a
1
6
type the interval for b
1
6
arr size is 16
now arr size is 15

Результат выполнения программы для 2<a<135 и 2<b<136:
type the interval for a
2
135
type the interval for b
2
136
arr size is 17556
now arr size is 16640

Статья получилась достаточно большой, а впереди еще две объемные задачи, в которых нужно разобрать логику перебора элементов. Остальные задачи разберем в следующей публикации.
Поделиться с друзьями
-->

Комментарии (46)


  1. gkislin
    06.10.2016 13:55
    #9844586
    +1

    Здравствуйте! Не скажу что не дружу с математикой и не знаю десятичной системы…
    Но- разверните плз вот это: s = 2r + 0.11q. Пример: q=1, r=2, получаем s=4.11 ??
    PS: я бы сделал также 2 цикла и проверял, что s есть одиночное число, отличное от q и r.


    1. gkislin
      06.10.2016 14:14
      #9844640

      Вот так получилось, немного сложнее:


              for (int q = 0; q < 10; q++) {
            for (int r = 1; r < 10; r++) {
                if ((r != q)) {
                    int res = 201 * r + 21 * q;
                    int s = res / 100;
                    if (s > 0 && s < 10 && s != r && s != q) {
                        res -= s * 100;
                        if (res / 10 == q && res % 10 == r) {
              System.out.println(String.format("%d%d%d+%d%d%d=%d%d%d", r, q, r, r, q, q, s, q, r));
                        }
                    }
                }
            }
        }


    1. SLASH_CyberPunk
      06.10.2016 14:33
      #9844668
      +1

      aba+abb=cba
      (100a+20b+a)+(100a+10b+b)=100c+10b+a
      201a+21b=100c+10b+a
      100c=200a+11b
      c = 2a + 0,11b


      1. LanSaid
        10.10.2016 12:45
        #9850044

        Очепятка в 2-ой строке: 100а + 10b + a


        1. SLASH_CyberPunk
          10.10.2016 12:57
          #9850070

          Да, поспешил и в уме частично просуммировал


    1. qark
      06.10.2016 19:42
      #9845186

      s = 2r + 0.11q не для любых r и q, а только для тех, которые удовлетворяют исходному равенству rqr + rqq = sqr.
      Кстати, из формулы s = 2r + 0.11q можно сразу сделать вывод, что q всегда равно нулю, и использовать только один цикл.


      1. ia_bobrova
        06.10.2016 19:44
        #9845190

        спасибо! да, так будет проще


  1. lnroma
    06.10.2016 14:32
    #9844664

    К стати формулу можно упростит s = 2r + 0.11q так как q = 0 всегда если смотреть на условие
    if (s % 1 == 0 && s != 0 && s < 10)

    так как все цифры дадут дробный остаток при суммирование.
    А это значит что можно обойтись одним циклом с проверкой на длину цифры т.е. число не большо 10

    public static void main(String[] args){
        int count = 0;
        for (int r = 1; r < 10; r++){
             double s = 2 * r ;
             if (s < 10) {
                    count++;
             }
         }
  }
  System.out.println("count is " + count);
}

    так же можно вынести проверку в if в цикл
    public static void main(String[] args){
        int count = 0;
        for (int r = 1; 2*r < 10; r++){
             count++;
         }
  }
  System.out.println("count is " + count);
}

    А так вы молодец, мало программистов женщин, так что это достойно уважения.
    p.s. равное 0 мы тоже не получим так как s=2*r+0.11*q а r по условию неравно 0;


    1. ia_bobrova
      06.10.2016 19:46
      #9845194

      спасибо!
      да, не заметила этот момент.


    1. Kapiton42
      07.10.2016 12:14
      #9846332

      Вы не находите обращение внимания на пол странным и даже оскорбительным? Зачем акцентировать внимание на том, что должно быть неважным для любого адекватного человека? У нас примерно 10-20% разработчиков девушки, и я ни разу не наблюдал, чтобы кто-либо обращал внимание на пол.


      1. ia_bobrova
        07.10.2016 12:19
        #9846344

        Пользователь написал

        мало программистов женщин
        Чем эта фраза отличается от Вашей?
        У нас примерно 10-20% разработчиков девушки


        1. Kapiton42
          07.10.2016 12:37
          #9846394

          Я не отрицаю этого факта. Я говорю, что как-либо выделять из-за этого девушек-программистов- странно, а тем более называть это достойным уважения. Такое чувство, как будто это ужасное бремя и на бедных программисток оказывается ужасное давление.


        1. lnroma
          07.10.2016 13:05
          #9846524

          Просто автор комментария. Пропитан западными ценностями, где женщины ходят на работу а мужчины сидят с детьми дома, обычно такие раскидываются словами «сексизм»,«гомофобия» и ищут к чему бы придраться.


  1. gkislin
    06.10.2016 16:26
    #9844900

    Те по большому счету — программа не нужна:) Раз q=0, для r остается всего (1,2,3,4), учитывая что 2*r<9


  1. masai
    06.10.2016 16:55
    #9844954

    1. В первой задаче встречается сравнение двух вещественных чисел, что само по себе уже плохо. Плюс одно из чисел получено умножением на число 0,11, которое непредставимо в виде конечной двоичной дроби (то есть гарантированно будут ошибки округления). Да, в этом случае всё сработало, но так писать не стоит.


    Вместо этого вполне можно было работать с целыми, используя равенство 100s = 220r + 11q. Какая разница, храним мы s в памяти или 100s? А при выводе на экран уже разделим.


    Ну и в целом решение "в лоб" не хуже на самом деле. Оно отрабатывает быстро, пишется быстрее и проще в понимании. Не нужно оптимизировать то, что не тормозит. Если, конечно, не стоит цель рассказать о другом интересном решении. ;)


    2. Факториал очень быстро растёт. 69! уже больше, чем 10^100. Поэтому лучше не считать его явно. (Да, кстати, в методе factorial у вас нет рекурсии.)


    Вместо этого можно смотреть на делители. Я бы попробовал такой метод: раскладываем число, на которое надо делить, на простые множители, потом находим максимум из произведений множителей на степени.


    Например:
    5 = 5^1. m = max {5*1} = 5.
    25 = 5^2. m = max {5*2} = 10.
    12 = 2^2 * 3^1. m = max {2*2, 3*1} = 4. (То есть 4! — это наименьший факториал, который делится на 12)


    Почему работает, надеюсь, понятно, а то объяснять долго. (Но я сейчас это придумал сходу, может проще можно.)


    На простые множители раскладывать тоже легко: делим на 2 пока делится и считаем сколько раз разделилось. Потом по нечётным числам: на 3, на 5, на 7 пока не получим единицу в частном.


    Наверное, если подумать, то и S как-то можно хитро упростить, но сходу ничего в голову не приходит. Это надо серьёзно с карандашом посидеть.


    3. Тоже через множители проще сделать.


    1. Stelet
      06.10.2016 20:06
      #9845242

      Извините, но произведение простого числа k на степень e не дает в результате минимальное число, факториал которого делится без остатка на k^e. Например, 8 = 2^3, m = 2*3 = 6 по вашему алгоритму. Тогда как правильный ответ 4.


      1. masai
        06.10.2016 23:46
        #9845572

        А, ну да. :) Вообще, решение работает, просто не выдаёт минимальное число. Под рукой бумаги не было проверить, а поспешил с комментарием.


        Тут была какая идея. Посмотреть, сколько раз (k) в факториал (m!) входит каждое простое число (p). Но я забыл что во множители факториала это число может входить несколько раз.


        В реальности там сложнее, конечно:
        k = [m/p] + [m/p^2] + [m/p^3] +… (квадратные скобки — округление вниз).


        Нужно для каждого простого множителя найти такой m, чтобы соответствующее k равнялось степени p в разложении аргумента s(n).


        В принципе, можно и перебором для m решать, так как показатели степеней не очень большие и число итераций будет не больше произведения простого множителя на его степень (как в первоначальном варианте). В любом случае быстрее вычисления факториалов, хотя решение, конечно усложняется.


  1. masai
    06.10.2016 16:59
    #9844962

    И да, если продолжить рассуждения в первой задаче, то она у вас одной команде вывода ответа на экран сведётся, так как там достаточно легко все цифры вручную найти. :)


  1. allnightlong
    06.10.2016 17:26
    #9845000
    +2

    Задача 2:

    поэтому для всех числовых переменных используем тип long (иначе вычисления будут некорректными)

    Неверно.

    В вашей реализации, начиная с m=26, метод factorial начнет возвращать отрицательные числа.
    Начиная с числа m=66, метод factorial начнет возвращать 0, после чего все проверки типа: 
    factorial(m) % n == 0

    становятся true. Т.е. фактически, максимальный факториал, который вычисляется (притом неправильно) — это факториал от 66, что несколько меньше необходимых 2400000.
    Правильный тип данных в данном случае — BigInteger.

    Но как только вы замените long -> BigInteger, то вы поймете, что ваш код никуда не годится.
    Вычислять факториал от двух с половиной миллионов, причем внутри двух циклов — это прямо по Горькому: «безумству храбрых поём мы славу».


    1. ia_bobrova
      06.10.2016 19:54
      #9845228

      спасибо!
      да, никуда не годится. буду править


  1. Tausinov
    06.10.2016 19:46
    #9845196

    Интересный способ упрощения в первой задаче, но на мой взгляд есть еще более простой вариант.
    rqr + rqq = sqr
    На число единиц в сумме влияет только сумма единиц слагаемых, т.е. r + q = r (строго говоря — (r + q) mod 10 = r), отсюда получается, что q может быть только нулем. Далее применяя Ваши рассуждения, получаем s = 2r. Тут уже перебор сводится к единственному циклу.


    1. fireSparrow
      08.10.2016 02:30
      #9848116

      перебор сводится к единственному циклу


      Этот перебор быстрее в уме сделать, чем цикл писать…


      1. Tausinov
        08.10.2016 12:45
        #9848306

        Согласен, но задачи ведь на программирование, вроде как.


  1. Anth
    06.10.2016 19:46
    #9845198

    Мне кажется, или в разборе задач приведеные решения как минимум неоптимальны?
    Например, в первой задаче ( rqr + rqq = sqr ) очевидно, что q=0 для уравнения r+q=10x+r, при r<10, q<10, x<10; а r<5 для уравнения r+r+x = s при r<10, s<10, x<10. Тогда можно ограничиться вообще одним циклом for, в котором будем перебирать r = [1,..,4] четыре шага вместо сотни)
    И вызывает подозрение третья задача — например повторения на уровне 9**2 = 3**4 можно отсечь еще до умножения (обозначим степень как **).


  1. EvgenijDv
    06.10.2016 19:46
    #9845200

    Метод factorial(long m) реализуем с помощью простой рекурсии: текущую переменную ret умножаем на переменную цикла for и затем присваиваем ей результат, пока не будут выполнены все итерации цикла.

    У вас что-то не так с рекурсией :-)


    1. ia_bobrova
      06.10.2016 19:49
      #9845204

      да, с терминологией ошиблась: тут обычный цикл


  1. rualekseev
    06.10.2016 19:49
    #9845206

    Про упрощение первой задачи
    rqr + rqq = sqr
    вычитаем из левой и правой части qr
    r00 + rqq = s00
    отсюда q = 0, 2r = s
    в итоге только один цикл for


  1. neutronah
    06.10.2016 19:49
    #9845208

    В задаче номер 2 вы вычисляли факториал семизначного числа? Вы уверены что результат поместится в переменную типа long?


  1. CrazyOpossum
    06.10.2016 19:49
    #9845210

    Решение к последней дало верный ответ на маленьких числах, а на больших проверять уже и не нужно?
    135^135 сильно не влазит в тип, по-хорошему надо либо подумать с карандашиком либо писать длинную арифметику. Питон в той же задачке даёт 16647.


  1. ser-mk
    06.10.2016 19:50
    #9845212

    Интересно мне одному так не повезло с порядком цифр в задаче с факториалом ?!)


    писал на питоне и перебор на 10 ядрах по моим подсчетам составлял 10 лет (=
    Пришлось от брутфорса отказаться, сделать именно поиск…
    P.S.
    я не сильный знаток Java, но как вы на типе long можно посчитать факториал?
    на С++ я уже при 25! получал переполнение 64 разрядного беззнакового типа


  1. fatum2996
    06.10.2016 19:50
    #9845216

    А разве во второй задаче не будет переполнения при вычислении факториала? Уже 21! не влезает в 64-битный long. Да и результат должен обеспокоить, если число простое, то оно должно прибавляться к результату. В интервале от 2300000 до 2400000 — 6791 простое число, значит результат должен быть не менее 6791 * 2300000 = 15619300000


  1. eugene_e
    06.10.2016 19:50
    #9845218

    Автор, ваше решение — это пример того, как не надо решать такие задачи. В первой задаче не надо использовать числа с плавающей запятой, потому что можно получить неправильный ответ из-за погрешности вычислений. Решение второй задачи — это вообще жесть. Вас не смущает, что вы можете попытаться найти факториал от 2400000 в худшем случае; при том, что даже 20! не помещается в long? В этой задаче можно вообще обойтись без вычисления факториала. Достаточно заметить, что все простые делители n должны входить в m!. Для этого надо разложить n на простые числа и потом из них составить m. Третье решение мне лень даже смотреть.
    PS. И почитайте что такое рекурсивная функция. Факториал можно вычислить с помощью рекурсивной функции, но у вас он находится как раз через цикл.


  1. Differentia
    06.10.2016 19:50
    #9845220

    Вторая задача решена неверно. Если n — простое, то s(n) = n. Отсюда, S(M, N) > sum(primes in [M, N]). Наименьшим простым в [2300000, 2400000] является 2300003, а кол-во простых >= 6800 (wolfram). Следовательно, имеем:
    6,596,625 = S(M, N) > sum(primes in [M, N]) > 2,300,003*6,800, что противоречиво. Прямая ошибка кроется в коде: (2*10^6)! явно не уместится в long. Также предполагаю, что решать задачу грубо вообще неприемлемо.


  1. Stelet
    06.10.2016 19:50
    #9845222

    Решение второй задачи в лоб для 100к чисел может и приемлимо по времени. Но в моем варианте требовалось, если не ошибаюсь, найти S(630000000, 640000000), и 10кк раз считать факториал неблагодарное занятие. У меня получился такой алгоритм:

    • Факторизируем число (раскладываем на простые множители)
    • В получившемся словаре формата {prime: degree}, где prime — простое число, а degree — его степень, проходим по ключам и находим для каждого из них минимальное число n такое, что n! mod prime ^prime = 0
    • Суммируем результат по всем числам в требуемом диапазоне


    На моем древнем ноуте посчиталось минут за 15.


    1. dima_sk8er
      09.10.2016 21:17
      #9849374

      У меня считалось около 0.2 с для диапазона [5300000, 5400000]. Для вашего случая (от 630000000 до 640000000) сейчас проверил, посчиталось примерно за минуту.


      Но алгоритм получения числа m придумал несколько иной:


      • единожды получаем все простые числа в нужном диапазоне (в моём случае от 2 до 5400000), используя решето Эратосфена;
      • раскладываем число на простые множители (пользуясь полученной таблицей простых чисел) и получаем список с множителями, причём множители могут повторяться;
      • предполагаем, что число m = 1;
      • для каждой группы множителей (группой назовём множители имеющие одинаковое значение) считаем количество элементов (N) в группе и выполняем следующее:
        1. берём первое число кратное множителю;
        2. делим его на множитель до тех пор, пока оно делится без остатка;
        3. количество раз, которое его удалось поделить, вычитаем из N;
        4. если N > 0, берем следующее число кратное множителю и переходим в п. 2;
        5. если данное число, кратное множителю, больше m, принимаем его за m и переходим к следующей группе;

      Код программы на C

      Алгоритм здесь не совсем соблюдается, так как не проиходит поиск количества элементов в группе, но суть остаётся та же.


      #include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *primes = NULL;

/* Ищет простые числа до числа count включительно.
 * Поиск производится по алгоритму "решето Эратосфена".
 * Возвращает 0 в случае успеха и 1 при ошибке. */
int init_primes(long count) {
    primes = (char *)malloc(count + 1);
    if (primes == NULL)
        return 1;

    memset(primes, 0xFF, count + 1);

    primes[0] = 0;
    primes[1] = 0;

    for (long k = 2; k*k <= count; k++)
        if (primes[k])
            for (long j = k*k; j <= count; j += k)
                primes[j] = 0;

    return 0;
}

// Минимальное количество делителей, под которые будет выделена память
#define MIN_DIVS 8

/* Возвращает массив простых делителей числа n, последний элемент массива - 0 */
long *get_divs(long n) {
    size_t count = 0;                   // Текущее количество делителей
    size_t size = MIN_DIVS;             // Размер массива с делителями

    long *divs = (long *)calloc(size, sizeof(long));
    if (divs == NULL) {
        fprintf(stderr, "Error: memory allocation failure\n");
        exit(1);
    }

    long div = 2;
    while (n != 1) {
        if (primes[n]) {
            if (count == size - 1)
                divs = realloc(divs, (size << 1) * sizeof(long));
            divs[count] = n;
            return divs;
        }

        if (n % div) {
            while (!primes[++div]);
            continue;
        }

        // Если текущего размера массива не хватает, выделим ещё памяти
        // помним так же, что в конце должен быть ноль (поэтому вычитаем 1)
        if (count == size - 1) {
            divs = realloc(divs, (size <<= 1) * sizeof(long));
            if (divs == NULL) {
                fprintf(stderr, "Error: memory reallocation failure\n");
                exit(2);
            }
        }

        divs[count++] = div;
        n /= div;
    }

    return divs;
}

/* Реализация функции s(n), данной в задании.
 * Для числа n ищет число m такое, что m! без остатка делится на n. */
long min_factorial(long n) {
    long *divs = get_divs(n);

    long *div = divs;
    long prev_div = *div;
    long max = 1;

    while (*div) {
        long k = *div;

        while (*div == prev_div) {
            if (k > max)
                max = k;

            long t = k;

            while (*div == prev_div && t % *div == 0) {
                t /= *div;
                div++;
            }

            if (*div != prev_div)
                break;
            k += *div;
        }

        prev_div = *div;
    }

    free(divs);
    return max;
}

int main(void) {
    if (init_primes(5400000)) {
        printf("Primes initialization error\n");
        return 1;
    }

    unsigned long sum = 0;
    for (long l = 5300000; l <= 5400000; l++)
        sum += min_factorial(l);

    printf("%lu\n", sum);

    free(primes);
    return 0;
}


      1. ia_bobrova
        09.10.2016 21:35
        #9849400

        Спасибо за идею!
        Надо переделать.


      1. Stelet
        09.10.2016 23:38
        #9849470

        У меня ровно тот же алгоритм, разве что в 1 пункте для границ [N, M] нет нужды считать все простые числа до верхней границы M, достаточно до sqrt(M) + 1. Ну и словарь простых множителей вместо списка, чтобы не искать каждый раз количество множителей в группе.


        1. vlanko
          10.10.2016 08:49
          #9849682

          Думаю, имеется в в иду быстрая проверка каждого числа диапазона на простоту, тогда s(n)=n;


  1. fireSparrow
    08.10.2016 03:52
    #9848132

    Попробовал для третьей задачи написать решение самостоятельно.
    Поскольку JAVA не знаю, писал на питоне:

    def foo(a1, a2, b1, b2):

    s = set()

    for a in range(a1+1, a2):
        for b in range(b1+1, b2):
            s.add(pow(a, b))

    return len(s)


    Это против 30 строк у автора статьи.


    1. ia_bobrova
      09.10.2016 21:30
      #9849394

      Метод pow(double a1, double a2, double b1, double b2) можно реализовать на добавлении элементов в HashSet, чтобы сразу же удалить все повторяющиеся элементы, тогда он тоже будет содержать всего шесть строк (убираем все строки, добавляющие наглядности).
      Не зря же Python отличается своей краткостью :)


  1. vlanko
    09.10.2016 21:17
    #9849376

    Я правильно вижу здесь код, какой хочет посчитать 2400000!, и вместить его в long?


  1. nickolaym
    10.10.2016 02:18
    #9849554

    В третьей задаче всё очень просто:
    a1^b1 == a2^b2, если a1 = a2^k, b2 = b1*k.

    То есть, берём 132*132 клеточки, и для каждого a прореживаем a^2,b=2i, a^3,b=3i,…

    Поскольку клеточек у нас мало, то вот такое простое решето с массивом и подсчётом количества оставшихся клеточек — оно и быстро, и просто.

    bool ab[135][135] = {}; // заполнено значениями false - т.е. "не покрашены ещё"
for(int a1=3; a1 < 135; ++a1) {
  for(int b1=2, a2=a1*a1; a2 < 135; b1+=1, a2*=a1) { // бежим по степеням числа a1
    for(int b2=b1; b2 < 135; b2+=b1) { // красим кратные степени
      ab[a2][b2] = true;  // "повторно использовано"
}}}
int count = 0;
for(int a1=3; a1 < 135; ++a1)
  for(int b1=3; b1 < 135; ++b1)
    if(!ab[a1][b1])
      ++count;


    Можно обойтись без таблицы, а посчитать, сколько дубликатов следует выкинуть.
    Для больших диапазонов так и следует поступать…


    1. ia_bobrova
      10.10.2016 15:01
      #9850308

      Спасибо!
      Теперь я понимаю, что с большими числами нужно быть аккуратнее.


      1. nickolaym
        11.10.2016 01:37
        #9851084
        +1

        Кстати говоря, построить множество степеней — тоже не такая уж плохая затея.
        Только надо понимать, что 134^134 — это очень большое число, и оно не влезет в double.
        Поэтому
        1) вместо a^b берём логарифм: log(a^b) = log(a)*b, где основание логарифма — по вкусу. Пусть даже натуральное
        2) прикидываем, какая точность нам нужна.
        Логарифмы 3..134 лежат на отрезке [1.0;5.0] и отличаются в 4 разряде; и умножаем на 3-значное число — то есть, нам, как минимум, 4+3 = 7 десятичных разряда нужны, чтобы не получить ложноположительный вердикт (признать неравные числа равными).
        С другой стороны, в 4 младших десятичных разрядах мантиссы размножается мусор — при умножении на максимум 134. Если мы не будем их отбрасывать, то получим ложноотрицательные вердикты (признаем равные числа неравными).
        А у double размер мантиссы — 16 десятичных разрядов. Отбросим 4 — останется 12, этого с избытком хватает для нашего случая.

        Таким образом, — тада, делаем множество.

        #include <iostream>
#include <set>
#include <cmath>

// сигнатура - некоторое число, уникально идентифицирующее нашу a^b
// в данном случае, это логарифм степени, как я уже сказал выше
double signature(int a, int b) {
	return floor(log(a) * b * 10000000); // возьмём 7 разрядов после запятой
}

int main() {
	std::set<double> signatures;
	for(int a = 3; a < 135; ++a) {
		for(int b = 3; b < 135; ++b) {
			double s = signature(a,b);
			signatures.insert(s);
		}
	}
	std::cout << signatures.size() << " уникальных чисел" << std::endl;
}

        Получаем 16515.


  1. ilnarb
    12.10.2016 22:37
    #9856312

    Первая задача решается аналитически, см. выше https://habrahabr.ru/post/311908/#comment_9845206
    Вторая и третья задача содержат факториал и степени на больших числах, что уже должно останавливать от попытки решать тупым перебором.

    Во второй надо разложить на множители x1^s1, ..., xk^sk: т.е. надо s1 штук x1,… И надо перебирать от 1 и далее числа, так же раскладывая на множители, и вычитать соответствующее количество, пока требуемое число si для всех xi не наберем. И так для диапазона чисел.

    Третий если перебирать то хотя бы как в https://habrahabr.ru/post/311908/#comment_9851084
    Иначе можно разложить на множители число A и кодировать степени в строку и вставлять строки в контейнер. Пример: 6^3=2^3*3^3, или 8^3=2^9.


  1. nickolaym
    13.10.2016 18:35
    #9858354

    По второй задаче.

    Строим массив простых чисел до N включительно. Если это не сделать, то разложение миллиона чисел на простые множители будет дорогой операцией (у меня на питоне это занимало 8 против 175 секунд).
    Надеюсь, не надо рассказывать, как просеивать числа за O(sqrt(n))?

    Далее, для каждого числа n из [M;N] делаем следующее:

    Раскладываем на простые множители. Даже не в виде пар «множитель, степень», а просто все множители подряд.
    Т.е. 240000 = [2, 2, 2, 2, 2, 2, 2, 3, 5, 5, 5, 5]
    Самое длинное разложение будет для 2^18 = 262144 :)

    Мысленно строим факториалы m! от 1 до много-много
    Каждое умножение на m — это мысленное добавление новых простых множителей.
    Просто берём и вычёркиваем эти множители из исходного разложения.

    [2, 2, 2, 2, 2, 2, 2, 3, 5, 5, 5, 5]
    2 :: [2, 2, 2, 2, 2, 2, 3, 5, 5, 5, 5]
    3 :: [2, 2, 2, 2, 2, 2, 5, 5, 5, 5]
    4 :: [2, 2, 2, 2, 5, 5, 5, 5]
    5 :: [2, 2, 2, 2, 5, 5, 5]
    6 :: [2, 2, 2, 5, 5, 5] и множитель 3 мы проигнорировали
    7 :: ничего не вычеркнули
    8 :: [5, 5, 5]
    9 :: ничего
    10 :: [5, 5] — а все 2 ещё раньше кончились
    11
    12
    13
    14
    15 :: [5]
    20 :: [] — о, победа!
    Таким образом, s(240000) = 20.

    Но бежать по m подряд очень опасно:
    230000 = [2, 2, 2, 2, 5, 5, 5, 5, 23]
    230001 = [3, 76667] — ого, какой перерывчик будет
    230002 = [2, 115001] — а здесь ещё больше
    230003 = [230003] — а тут вообще простое число, s(230003) = 230003
    230004 = [2, 2, 3, 3, 6389]

    Поэтому делаем следующим образом
    Вычёркиваем множители, входящие в m
    Находим следующее m' > m, делящееся хоть на один из наших множителей
    — для каждого множителя строим гипотезу m' = m + (p — m mod p) — т.е. ближайшее округлённое вверх
    — среди этих гипотез выбираем минимум

    230000 = [2, 2, 2, 2, 5, 5, 5, 5, 23]
    2 :: [2, 2, 2, 5, 5, 5, 5, 23] ==> m' = min{4, 5, 23} = 4 — про 3 ни слова
    4 :: [2, 5, 5, 5, 23] ==> m' = min{6, 5, 23} = 5 — обратите внимание, что минимум достигнут не на младшем множителе
    5 :: [2, 5, 5, 23] ==> m' = min{6, 10, 23} = 6
    6 :: [5, 5, 23] ==> m' = min{10, 23} = 10
    10 :: [5, 23] ==> m' = min{15, 23} = 15
    15 :: [23] ==> m' = min{23} = 23
    23 :: []
    s(230000) = 23.

    На всякий случай, — сходу отвергнем гипотезу, что s(n) равно максимальному простому множителю или что-то в таком роде.
    230187 = [3, 277, 277] — s = 554 (=227*2)
    230318 = [2, 11, 19, 19, 29] — s = 38 (вообще не делится на 29)

    Ну вот. Когда мы научились быстро находить s для любого числа (не превосходящего N, потому что простые числа мы только дотуда нагенерировали),
    осталось только пробежать по всему диапазону [M,N] и просуммировать.

    Мы потратим на это всё время порядка O((N-M) * log(N)^2).
    Ну и O(N*sqrt(N)) на таблицу простых чисел.

    Заметьте! Ни длинная арифметика, ни тугие забеги за квадратичное время не понадобились.