Что спрашивают
Найдите первые пять чисел строго больше A, представимых произведением ровно двух простых множителей. Множители могут совпадать. В записи каждого из них комбинация 16 должна встретиться ровно один раз.
Для каждого числа выведите его и меньший простой множитель. В тренировочной версии A не больше 20 000 000. Условие относится к записи множителей, а не к записи их произведения.
Приём решения
Пусть n = p × q и p ≤ q. Тогда p не больше √n. Переберём только простые p, содержащие ровно одно вхождение 16. Если p делит n, проверим частное q: оно тоже должно быть простым и иметь ровно одно вхождение.
- Получите малые простые решетом и оставьте подходящие по записи.
- Перебирайте нечётные n, начиная строго после A. Чётное произведение содержало бы простой множитель 2, который не имеет комбинации 16.
- Для каждого n проверяйте подходящие p до корня включительно.
- На найденном делителе вычислите q и проверьте оба свойства частного.
- Сохраните пару и закончите после пяти ответов.
Если q составное, у n больше двух простых множителей с учётом повторений; другая пара простых это не исправит. Если q простое, разложение уже определено. Поэтому после первого подходящего простого делителя проверка n может закончиться.
Для квадрата p² меньший множитель равен корню, и он должен попасть в перебор. А у p³ после выделения p частное p² составное — такой кандидат не подходит.
Список простых строится до корня текущего запаса границы. Когда поиск выходит за запас, граница удваивается и список перестраивается: произвольного конечного предела поиска в коде нет. Для каждого n перебирается небольшой отфильтрованный список; память малого решета имеет порядок √U для текущего запаса U.
Разбор на примере
Ввод
27000
Вывод
27221 163 27889 167 189569 163 194221 167 260963 163
| Число | Простые множители | Проверка |
|---|---|---|
| 27221 | 163 × 167 | В каждом по одному 16 |
| 27889 | 167 × 167 | Квадрат разрешён |
| 189569 | 163 × 1163 | Разная длина записей разрешена |
| 194221 | 167 × 1163 | Оба простые |
| 260963 | 163 × 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)
<algorithm>
<cmath>
<iostream>
<string>
<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 равный единице.