Чефір загубився#366

Чефір загубився (Розбір)

Автор задачі:

Ціцей Павло

Задачу підготував:

Фейса Богдан

Розбір написав:

Фейса Богдан

У цій задачі будемо розглядати кучу випадків. Треба помітити, що за допомогою операцій, тільки зменшується.

  • x\equiv n\equiv 0 \bmod 2. У такому випадку можна виконувати операцію , тобто віднімати від найменший дільник, який більший за . Бо парне, то цей дільник буде , тому n\rightarrow n-2. При тому, парність не змінилась. Оскільки також парне, то рано чи пізно такими операціями ми зробимо з число .

  • x\equiv 0 \bmod 2 та n\equiv 1 \bmod 2. Будемо зводити цей випадок до першого. Зробимо знову операцію . Зверніть увагу, що дільник, який ми віднімемо від , буде непарним, бо якби він був парним, то б ділилось на , але непарне.

  • x\equiv 1 \bmod 2 та n\equiv 0 \bmod 2. Спочатку, зведемо до за допомогою першого випадку. Після цього, найбільший дільник буде \frac{n}{2}, бо n=2x, тому використовуємо другу операцію і зводимо до . Також, тут треба розглянути випадок, коли n<2x та вивести "NO".

  • x\equiv n\equiv 1 \bmod 2. Віднімаємо від найменший дільник, який буде непарним, та повторюємо алгоритм з третього способу.