Ділиться чи ні#13059

Ділиться чи ні (Розбір)

Автор задачі:	Andrii Kholod (Connect)
Підготував:	Andrii Kholod (Connect)
Розбір:	Andrii Kholod (Connect)

Розв'язання

Нехай перше число, яке вибрав Андрій, дорівнює $x$ . Тоді масив має вигляд

$x, x + 1, x + 2, \dots, x + n - 1.$ x, x+1, x+2, \ldots, x+n-1.

Спочатку розглянемо випадок $m = 2$ m=2.

Якщо $n = 1$ n=1, Андрій може вибрати непарне число, тому Тарас не зможе виграти.

Якщо $n \geq 2$ n\ge 2, то серед будь-яких двох послідовних цілих чисел є парне, тому Тарас може вибрати підвідрізок, що складається лише з цього числа.

Отже, для $m = 2$ m=2 Тарас виграє тоді й лише тоді, коли $n \geq 2$ n\ge 2.

Тепер нехай $m$ непарне.

Якщо $n \geq m$ n\ge m, Тарас може вибрати будь-які $m$ послідовних елементів. Їх сума ділиться на $m$ , тому Тарас завжди виграє.

Тепер розглянемо випадок $n < m$ n<m.

Нехай $P_{k}$ P_k — сума перших $k$ елементів. Маємо

$P_{k} = k x + \frac{k ( k - 1 )}{2} .$ P_k = kx + \frac{k(k-1)}{2}.

Будь-який непорожній підвідрізок можна подати у вигляді $P_{j} - P_{i}$ P_j-P_i для деяких $0 \leq i < j \leq n$ 0\le i<j\le n.

Його сума дорівнює

$P_{j} - P_{i} = (j - i) (x + \frac{i + j - 1}{2}) .$ P_j-P_i = (j-i)\left(x+\frac{i+j-1}{2}\right).

Оскільки $1 \leq j - i \leq n < m$ 1\le j-i\le n<m і $m$ є простим, число $j - i$ j-i не ділиться на $m$ .

Також, оскільки $m$ непарне, число $2$ має обернений елемент за модулем $m$ .

Тому сума підвідрізка ділиться на $m$ тоді й лише тоді, коли

$2 x + i + j - 1 \equiv 0 (mod m) .$ 2x+i+j-1 \equiv 0 \pmod m.

Еквівалентно,

$i + j \equiv 1 - 2 x (mod m) .$ i+j \equiv 1-2x \pmod m.

Зауважимо, що для всіх пар $0 \leq i < j \leq n$ 0\le i<j\le n значення $i + j$ i+j може набувати кожного цілого значення від $1$ до $2 n - 1$ 2n-1.

Отже, якщо

$2 n - 1 \geq m,$ 2n-1\ge m,

то серед цих значень є представники всіх можливих лишків за модулем $m$ . Тому незалежно від значення $x$ Тарас завжди зможе знайти відповідний непорожній підвідрізок.

З іншого боку, якщо

$2 n - 1 < m,$ 2n-1<m,

то значення $1, 2, \dots, 2 n - 1$ 1,2,\ldots,2n-1 не покривають усі лишки за модулем $m$ .

Оскільки $m$ — непарне просте число, при зміні $x$ значення $1 - 2 x$ 1-2x може набувати будь-якого лишку за модулем $m$ . Тому Андрій може вибрати таке $x$ , що $1 - 2 x$ 1-2x не представлене серед $1, 2, \dots, 2 n - 1$ 1,2,\ldots,2n-1.

У такому випадку Тарас не зможе знайти підвідрізок, сума якого ділиться на $m$ .

Отже, у всіх випадках Тарас виграє тоді й лише тоді, коли

$2 n - 1 \geq m .$ 2n-1\ge m.

Часова складність розв'язання — $O (1)$ .

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m;
    cin >> n >> m;

    if (2 * n - 1 >= m)
        cout << "Taras\n";
    else
        cout << "Andrii\n";

    return 0;
}

C++