Что спрашивают
M — разность максимального и минимального простых делителей числа, не считая самого числа. Каждый простой делитель учитывается один раз. Для простого числа или степени одного простого M равна нулю.
Нужны первые пять чисел строго больше A, для которых M простая и содержит не менее четырёх цифр 1. Выводятся пары «число, M». В тренировочной задаче A не больше 10^8.
Приём решения
Например, у 60 разные простые делители — 2, 3, 5, поэтому M равна 5 - 2 = 3. Повторение множителя в разложении не меняет минимум или максимум: у 72 это всё равно 2 и 3. Не нужно брать крайние делители вообще — они могут быть составными.
Подходящих чисел может быть мало. Разложение каждого кандидата отдельным длинным перебором повторяет много работы. Обработаем блок из 4096 соседних чисел. Это размер порции вычислений; поиск не ограничивается одним блоком.
- Решетом получите простые до квадратного корня правой границы блока.
- Для каждого числа храните остаток после деления, минимальный и максимальный обнаруженные простые делители.
- Для очередного простого p пройдите только по его кратным в блоке. Запомните p и разделите остаток на все степени p.
- После всех малых простых остаток больше единицы может быть только простым. Учтите его при выборе максимального делителя.
- Для каждого числа вычислите разность. Сначала проверьте число единиц, затем простоту M.
- Просматривайте блоки и числа в них по возрастанию; остановитесь после пяти строк.
Остаток простого числа, для которого не было малых делителей, не добавляется как собственный делитель: его 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 | Отбор |
|---|---|---|---|
| 22226 | 2, 11113 | 11111 | Составная M: пропускаем |
| 22238 | 2, 11119 | 11117 | Подходит |
| 22346 | 2, 11173 | 11171 | Подходит |
| 44476 | 2, 11119 | 11117 | Повтор 2 не меняет M |
| 44692 | 2, 11173 | 11171 | Подходит |
| 66714 | 2, 3, 11119 | 11117 | Средний делитель не меняет 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)
<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;
}
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. - Заменить «не менее» на «ровно»
Разность с большим количеством единиц тоже подходит. Проверка количества должна быть нестрогой снизу.
- Остановиться после одного блока
Блок задаёт только способ обработки. Следующие числа продолжают проверяться, пока не найдены пять ответов.