Автор задачі: | Ціцей Павло |
Задачу підготував: | Фейса Богдан |
Розбір написав: | Фейса Богдан |
У цій задачі будемо розглядати кучу випадків. Треба помітити, що за допомогою операцій, тільки зменшується.
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. Віднімаємо від найменший дільник, який буде непарним, та повторюємо алгоритм з третього способу.