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

У меня считалось около 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;
}