Что спрашивают

M — разность максимального и минимального простых делителей числа, не считая самого числа. Каждый простой делитель учитывается один раз. Для простого числа или степени одного простого M равна нулю.

Нужны первые пять чисел строго больше A, для которых M простая и содержит не менее четырёх цифр 1. Выводятся пары «число, M». В тренировочной задаче A не больше 10^8.

Приём решения

Например, у 60 разные простые делители — 2, 3, 5, поэтому M равна 5 - 2 = 3. Повторение множителя в разложении не меняет минимум или максимум: у 72 это всё равно 2 и 3. Не нужно брать крайние делители вообще — они могут быть составными.

Подходящих чисел может быть мало. Разложение каждого кандидата отдельным длинным перебором повторяет много работы. Обработаем блок из 4096 соседних чисел. Это размер порции вычислений; поиск не ограничивается одним блоком.

  1. Решетом получите простые до квадратного корня правой границы блока.
  2. Для каждого числа храните остаток после деления, минимальный и максимальный обнаруженные простые делители.
  3. Для очередного простого p пройдите только по его кратным в блоке. Запомните p и разделите остаток на все степени p.
  4. После всех малых простых остаток больше единицы может быть только простым. Учтите его при выборе максимального делителя.
  5. Для каждого числа вычислите разность. Сначала проверьте число единиц, затем простоту M.
  6. Просматривайте блоки и числа в них по возрастанию; остановитесь после пяти строк.

Остаток простого числа, для которого не было малых делителей, не добавляется как собственный делитель: его M оставляем нулём. У чисел с единственным различным простым делителем разность также получается нулевой.

Список малых простых покрывает и проверку M: для составного n его простые делители меньше n, следовательно M < n. Проверки до корня правой границы блока достаточно. Разность может содержать не меньше четырёх единиц и всё же быть составной: 11111 = 41 × 271.

Для блока ширины W и верхней границы U проход по кратным требует порядка суммы W/p + 1 по малым простым, плюс удаления их степеней. Память — O(W + √U). Такая обработка заменяет отдельный проход до корня для каждого числа.

Разбор на примере

Ввод

22000

Вывод

22238 11117
22346 11171
44476 11117
44692 11171
66714 11117
Разбор примера по шагам
ЧислоРазные простые делителиMОтбор
222262, 1111311111Составная M: пропускаем
222382, 1111911117Подходит
223462, 1117311171Подходит
444762, 1111911117Повтор 2 не меняет M
446922, 1117311171Подходит
667142, 3, 1111911117Средний делитель не меняет M

Первые два подходящих числа после границы — 22238 и 22346. Для 44476 и 44692 добавилась ещё одна двойка в разложении, но различные простые делители и M остались прежними. В 66714 появился делитель 3, однако крайними по-прежнему являются 2 и 11119. До пятого ответа приходится просмотреть несколько блоков.

Код на Python и C++

Числа в каждом блоке проверяются по порядку. Оставшийся после делений простой множитель учитывается через max(high[i], rest[i]); без него можно потерять крупнейший делитель.

В C++ решето хранится в vector<bool>, а целый корень считает своя функция isqrt: sqrtl с поправкой на единицу в обе стороны, чтобы погрешность не сдвинула границу. Единицы в записи считает count по строке to_string(m).

import sys
from math import isqrt


def primes_to(limit):
    if limit < 2:
        return []
    flags = bytearray(b'\x01') * (limit + 1)
    flags[0:2] = b'\x00\x00'
    for p in range(2, isqrt(limit) + 1):
        if flags[p]:
            flags[p * p:limit + 1:p] = b'\x00' * ((limit - p * p) // p + 1)
    return [p for p in range(2, limit + 1) if flags[p]]


def is_prime(n, primes):
    if n < 2:
        return False
    for p in primes:
        if p * p > n:
            break
        if n % p == 0:
            return False
    return True


def gap_values(start, end, primes):
    rest = list(range(start, end + 1))
    low = [0] * len(rest)
    high = [0] * len(rest)
    for p in primes:
        if p * p > end:
            break
        first = max(p * p, (start + p - 1) // p * p)
        for n in range(first, end + 1, p):
            i = n - start
            if low[i] == 0:
                low[i] = p
            high[i] = p
            while rest[i] % p == 0:
                rest[i] //= p
    return [max(high[i], rest[i]) - low[i] if low[i] else 0
            for i in range(len(rest))]


def solve(a, count=5):
    rows = []
    start = a + 1
    while len(rows) < count:
        end = start + 4095
        primes = primes_to(isqrt(end))
        for i, m in enumerate(gap_values(start, end, primes)):
            if str(m).count('1') >= 4 and is_prime(m, primes):
                rows.append((start + i, m))
                if len(rows) == count:
                    return rows
        start = end + 1
    return rows

if __name__ == '__main__':
    a = int(sys.stdin.read())
    rows = solve(a)
    for row in rows:
        print(*row)
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long isqrt(long long n) {
    long long r = sqrtl(n);
    while (r * r > n)
        r -= 1;
    while ((r + 1) * (r + 1) <= n)
        r += 1;
    return r;
}

vector<long long> primes_to(long long limit) {
    vector<long long> primes;
    if (limit < 2)
        return primes;
    vector<bool> flags(limit + 1, true);
    for (long long p = 2; p <= limit; p++) {
        if (!flags[p])
            continue;
        primes.push_back(p);
        for (long long k = p * p; k <= limit; k += p)
            flags[k] = false;
    }
    return primes;
}

bool is_prime(long long n, const vector<long long>& primes) {
    if (n < 2)
        return false;
    for (long long p : primes) {
        if (p * p > n)
            break;
        if (n % p == 0)
            return false;
    }
    return true;
}

vector<long long> gap_values(long long start, long long end, const vector<long long>& primes) {
    int size = end - start + 1;
    vector<long long> rest(size), low(size, 0), high(size, 0);
    for (int i = 0; i < size; i++)
        rest[i] = start + i;
    for (long long p : primes) {
        if (p * p > end)
            break;
        long long first = max(p * p, (start + p - 1) / p * p);
        for (long long n = first; n <= end; n += p) {
            int i = n - start;
            if (low[i] == 0)
                low[i] = p;
            high[i] = p;
            while (rest[i] % p == 0)
                rest[i] /= p;
        }
    }
    vector<long long> result(size);
    for (int i = 0; i < size; i++)
        result[i] = low[i] ? max(high[i], rest[i]) - low[i] : 0;
    return result;
}

int main() {
    long long a;
    cin >> a;
    int found = 0;
    long long start = a + 1;
    while (found < 5) {
        long long end = start + 4095;
        vector<long long> primes = primes_to(isqrt(end));
        vector<long long> values = gap_values(start, end, primes);
        for (int i = 0; i < (int)values.size() && found < 5; i++) {
            long long m = values[i];
            string text = to_string(m);
            if (count(text.begin(), text.end(), '1') >= 4 && is_prime(m, primes)) {
                cout << start + i << ' ' << m << '\n';
                found += 1;
            }
        }
        start = end + 1;
    }
}

Типичные ошибки

  • Вычитать крайние делители, не проверяя простоту

    Максимальный собственный делитель часто составной. M определяется только различными простыми делителями.

  • Считать повторения одного простого разными делителями

    У степени простого крайние простые делители совпадают. Их разность равна нулю независимо от показателя степени.

  • Проверить только количество единиц

    Условие требует ещё и простоту M. Число 11111 содержит пять единиц, но составное: 11111 = 41 × 271.

  • Заменить «не менее» на «ровно»

    Разность с большим количеством единиц тоже подходит. Проверка количества должна быть нестрогой снизу.

  • Остановиться после одного блока

    Блок задаёт только способ обработки. Следующие числа продолжают проверяться, пока не найдены пять ответов.