Разбор задач заочного тура школы программистов HeadHunter 2016. Часть 1

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

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


              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
        aba+abb=cba
        (100a+20b+a)+(100a+10b+b)=100c+10b+a
        201a+21b=100c+10b+a
        100c=200a+11b
        c = 2a + 0,11b
          0
          Очепятка в 2-ой строке: 100а + 10b + a
            0
            Да, поспешил и в уме частично просуммировал
          0
          s = 2r + 0.11q не для любых r и q, а только для тех, которые удовлетворяют исходному равенству rqr + rqq = sqr.
          Кстати, из формулы s = 2r + 0.11q можно сразу сделать вывод, что q всегда равно нулю, и использовать только один цикл.
            0
            спасибо! да, так будет проще
          0
          К стати формулу можно упростит 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;
            0
            спасибо!
            да, не заметила этот момент.
              0
              Вы не находите обращение внимания на пол странным и даже оскорбительным? Зачем акцентировать внимание на том, что должно быть неважным для любого адекватного человека? У нас примерно 10-20% разработчиков девушки, и я ни разу не наблюдал, чтобы кто-либо обращал внимание на пол.
                0
                Пользователь написал
                мало программистов женщин
                Чем эта фраза отличается от Вашей?
                У нас примерно 10-20% разработчиков девушки

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

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

                  0

                  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. Тоже через множители проще сделать.

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

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


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


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


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


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

                    0

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

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

                      Неверно.

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

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

                      Но как только вы замените long -> BigInteger, то вы поймете, что ваш код никуда не годится.
                      Вычислять факториал от двух с половиной миллионов, причем внутри двух циклов — это прямо по Горькому: «безумству храбрых поём мы славу».
                        0
                        спасибо!
                        да, никуда не годится. буду править
                        0
                        Интересный способ упрощения в первой задаче, но на мой взгляд есть еще более простой вариант.
                        rqr + rqq = sqr
                        На число единиц в сумме влияет только сумма единиц слагаемых, т.е. r + q = r (строго говоря — (r + q) mod 10 = r), отсюда получается, что q может быть только нулем. Далее применяя Ваши рассуждения, получаем s = 2r. Тут уже перебор сводится к единственному циклу.
                          0
                          перебор сводится к единственному циклу


                          Этот перебор быстрее в уме сделать, чем цикл писать…
                            0
                            Согласен, но задачи ведь на программирование, вроде как.
                          0
                          Мне кажется, или в разборе задач приведеные решения как минимум неоптимальны?
                          Например, в первой задаче ( 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 можно отсечь еще до умножения (обозначим степень как **).
                            0
                            Метод factorial(long m) реализуем с помощью простой рекурсии: текущую переменную ret умножаем на переменную цикла for и затем присваиваем ей результат, пока не будут выполнены все итерации цикла.

                            У вас что-то не так с рекурсией :-)
                              0
                              да, с терминологией ошиблась: тут обычный цикл
                              0
                              Про упрощение первой задачи
                              rqr + rqq = sqr
                              вычитаем из левой и правой части qr
                              r00 + rqq = s00
                              отсюда q = 0, 2r = s
                              в итоге только один цикл for
                                0
                                В задаче номер 2 вы вычисляли факториал семизначного числа? Вы уверены что результат поместится в переменную типа long?
                                  0
                                  Решение к последней дало верный ответ на маленьких числах, а на больших проверять уже и не нужно?
                                  135^135 сильно не влазит в тип, по-хорошему надо либо подумать с карандашиком либо писать длинную арифметику. Питон в той же задачке даёт 16647.
                                    0
                                    Интересно мне одному так не повезло с порядком цифр в задаче с факториалом ?!)


                                    писал на питоне и перебор на 10 ядрах по моим подсчетам составлял 10 лет (=
                                    Пришлось от брутфорса отказаться, сделать именно поиск…
                                    P.S.
                                    я не сильный знаток Java, но как вы на типе long можно посчитать факториал?
                                    на С++ я уже при 25! получал переполнение 64 разрядного беззнакового типа
                                      0
                                      А разве во второй задаче не будет переполнения при вычислении факториала? Уже 21! не влезает в 64-битный long. Да и результат должен обеспокоить, если число простое, то оно должно прибавляться к результату. В интервале от 2300000 до 2400000 — 6791 простое число, значит результат должен быть не менее 6791 * 2300000 = 15619300000
                                        0
                                        Автор, ваше решение — это пример того, как не надо решать такие задачи. В первой задаче не надо использовать числа с плавающей запятой, потому что можно получить неправильный ответ из-за погрешности вычислений. Решение второй задачи — это вообще жесть. Вас не смущает, что вы можете попытаться найти факториал от 2400000 в худшем случае; при том, что даже 20! не помещается в long? В этой задаче можно вообще обойтись без вычисления факториала. Достаточно заметить, что все простые делители n должны входить в m!. Для этого надо разложить n на простые числа и потом из них составить m. Третье решение мне лень даже смотреть.
                                        PS. И почитайте что такое рекурсивная функция. Факториал можно вычислить с помощью рекурсивной функции, но у вас он находится как раз через цикл.
                                          0
                                          Вторая задача решена неверно. Если 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. Также предполагаю, что решать задачу грубо вообще неприемлемо.
                                            0
                                            Решение второй задачи в лоб для 100к чисел может и приемлимо по времени. Но в моем варианте требовалось, если не ошибаюсь, найти S(630000000, 640000000), и 10кк раз считать факториал неблагодарное занятие. У меня получился такой алгоритм:

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


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

                                              У меня считалось около 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;
                                              }
                                                0
                                                Спасибо за идею!
                                                Надо переделать.
                                                  0
                                                  У меня ровно тот же алгоритм, разве что в 1 пункте для границ [N, M] нет нужды считать все простые числа до верхней границы M, достаточно до sqrt(M) + 1. Ну и словарь простых множителей вместо списка, чтобы не искать каждый раз количество множителей в группе.
                                                    0
                                                    Думаю, имеется в в иду быстрая проверка каждого числа диапазона на простоту, тогда s(n)=n;
                                                0
                                                Попробовал для третьей задачи написать решение самостоятельно.
                                                Поскольку 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 строк у автора статьи.
                                                  0
                                                  Метод pow(double a1, double a2, double b1, double b2) можно реализовать на добавлении элементов в HashSet, чтобы сразу же удалить все повторяющиеся элементы, тогда он тоже будет содержать всего шесть строк (убираем все строки, добавляющие наглядности).
                                                  Не зря же Python отличается своей краткостью :)
                                                  0
                                                  Я правильно вижу здесь код, какой хочет посчитать 2400000!, и вместить его в long?
                                                    0
                                                    В третьей задаче всё очень просто:
                                                    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;
                                                    


                                                    Можно обойтись без таблицы, а посчитать, сколько дубликатов следует выкинуть.
                                                    Для больших диапазонов так и следует поступать…
                                                      0
                                                      Спасибо!
                                                      Теперь я понимаю, что с большими числами нужно быть аккуратнее.
                                                        +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.
                                                      0
                                                      Первая задача решается аналитически, см. выше 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.
                                                        0
                                                        По второй задаче.

                                                        Строим массив простых чисел до 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)) на таблицу простых чисел.

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

                                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                        Самое читаемое