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

Найдите первые пять чисел строго больше A, представимых произведением ровно двух простых множителей. Множители могут совпадать. В записи каждого из них комбинация 16 должна встретиться ровно один раз.

Для каждого числа выведите его и меньший простой множитель. В тренировочной версии A не больше 20 000 000. Условие относится к записи множителей, а не к записи их произведения.

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

Пусть n = p × q и p ≤ q. Тогда p не больше √n. Переберём только простые p, содержащие ровно одно вхождение 16. Если p делит n, проверим частное q: оно тоже должно быть простым и иметь ровно одно вхождение.

  1. Получите малые простые решетом и оставьте подходящие по записи.
  2. Перебирайте нечётные n, начиная строго после A. Чётное произведение содержало бы простой множитель 2, который не имеет комбинации 16.
  3. Для каждого n проверяйте подходящие p до корня включительно.
  4. На найденном делителе вычислите q и проверьте оба свойства частного.
  5. Сохраните пару и закончите после пяти ответов.

Если q составное, у n больше двух простых множителей с учётом повторений; другая пара простых это не исправит. Если q простое, разложение уже определено. Поэтому после первого подходящего простого делителя проверка n может закончиться.

Для квадрата p² меньший множитель равен корню, и он должен попасть в перебор. А у p³ после выделения p частное p² составное — такой кандидат не подходит.

Список простых строится до корня текущего запаса границы. Когда поиск выходит за запас, граница удваивается и список перестраивается: произвольного конечного предела поиска в коде нет. Для каждого n перебирается небольшой отфильтрованный список; память малого решета имеет порядок √U для текущего запаса U.

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

Ввод

27000

Вывод

27221 163
27889 167
189569 163
194221 167
260963 163
Разбор примера по шагам
ЧислоПростые множителиПроверка
27221163 × 167В каждом по одному 16
27889167 × 167Квадрат разрешён
189569163 × 1163Разная длина записей разрешена
194221167 × 1163Оба простые
260963163 × 1601Меньший множитель — 163

После границы 27000 первое число 27221 даёт разные простые 163 и 167. Следующее 27889 — квадрат 167; он не исключается. У 1163 и 1601 тоже ровно одно вхождение 16. Между ответами есть большие промежутки, поэтому выводим первые пять по порядку чисел, а не по порядку рассмотрения множителей.

Код на Python и C++

Список primes покрывает проверку простоты частного: q не больше текущего n. Равенство p² = n разрешено проверкой остановки только при строгом превышении.

В C++ вхождения 16 считает функция count16: она проверяет пары соседних цифр в to_string(n). Решето хранится в vector<bool>.

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 solve(a, count=5):
    n = a + 1
    if n % 2 == 0:
        n += 1
    ceiling = max(300000, 2 * n)
    primes = primes_to(isqrt(ceiling))
    eligible = [p for p in primes if str(p).count('16') == 1]
    rows = []
    while len(rows) < count:
        if n > ceiling:
            ceiling *= 2
            primes = primes_to(isqrt(ceiling))
            eligible = [p for p in primes if str(p).count('16') == 1]
        for p in eligible:
            if p * p > n:
                break
            if n % p == 0:
                q = n // p
                if str(q).count('16') == 1 and is_prime(q, primes):
                    rows.append((n, p))
                break
        n += 2
    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;
}

// Сколько раз 16 встречается в записи числа.
int count16(long long n) {
    string text = to_string(n);
    int count = 0;
    for (size_t i = 0; i + 1 < text.size(); i++)
        count += text[i] == '1' && text[i + 1] == '6';
    return count;
}

vector<long long> eligible_primes(const vector<long long>& primes) {
    vector<long long> eligible;
    for (long long p : primes) {
        if (count16(p) == 1)
            eligible.push_back(p);
    }
    return eligible;
}

int main() {
    long long a;
    cin >> a;
    long long n = a + 1;
    if (n % 2 == 0)
        n += 1;
    long long ceiling = max(300000LL, 2 * n);
    vector<long long> primes = primes_to(isqrt(ceiling));
    vector<long long> eligible = eligible_primes(primes);
    int found = 0;
    while (found < 5) {
        if (n > ceiling) {
            ceiling *= 2;
            primes = primes_to(isqrt(ceiling));
            eligible = eligible_primes(primes);
        }
        for (long long p : eligible) {
            if (p * p > n)
                break;
            if (n % p == 0) {
                long long q = n / p;
                if (count16(q) == 1 && is_prime(q, primes)) {
                    cout << n << ' ' << p << '\n';
                    found += 1;
                }
                break;
            }
        }
        n += 2;
    }
}

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

  • Требовать разные множители

    Квадрат подходящего простого имеет ровно два множителя с учётом повторений и удовлетворяет условию.

  • Проверить комбинацию только у одного множителя

    И p, и q должны содержать ровно одно вхождение 16. Свойство одного не заменяет свойство другого.

  • Не проверить простоту частного

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

  • Заменить ровно одно на наличие

    Проверка через in пропустит записи с несколькими вхождениями. Требуется count равный единице.