Розберемося, що означає кожне висловлювання. Людина з номером (для i < n) стверджує: «усі люди з номерами, кратними i+1, — брехуни». Людина з номером мовчить.
Оскільки лицар каже правду, а брехун бреше, для кожного i < n маємо точну рівносильність:
Тепер ключове спостереження: усі кратні числа i+1, які не перевищують , строго більші за (найменше з них — це саме i+1). Тому статус людини повністю визначається статусами людей з більшими номерами.
Звідси випливає, що вся розстановка однозначно відновлюється, щойно ми зафіксуємо статус останньої людини. А вона нічого не сказала, тому обидва варіанти допустимі — усього маємо рівно дві можливі конфігурації.
Алгоритм такий: беремо припущення про статус людини (лицар або брехун) і йдемо вниз від i = n-1 до , щоразу перевіряючи всі кратні числа i+1: якщо серед них є хоча б один лицар, то людина — брехун, інакше — лицар. Порахувавши лицарів, повторюємо те саме для другого припущення. Відповідь — менше з двох чисел при k = 0 і більше при k = 1.
Складність: для кожного ми перебираємо кратні до i+1, тобто приблизно n/(i+1) значень. Разом це гармонічна сума
що при n \le 10^5 становить близько 1.2 \cdot 10^6 операцій — цілком швидко. Обидва прогони роблять це двічі.