Divisible or Not (Editorial)

Solution

Let the first number chosen by Andrii be $x$. Then the array has the form

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

First, consider the case m=2.

If n=1, Andrii can choose an odd number, so Taras cannot win.

If n\ge 2, among any two consecutive integers there is an even one, so Taras can choose a subsegment consisting only of this number.

Therefore, for m=2, Taras wins if and only if n\ge 2.

Now suppose that $m$ is odd.

If n\ge m, Taras can choose any $m$ consecutive elements. Their sum is divisible by $m$, so Taras always wins.

Now consider the case n<m.

Let P_k be the sum of the first $k$ elements. We have

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

A non-empty subsegment can be represented as P_j-P_i for some 0\le i<j\le n.

Its sum is

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

Since 1\le j-i\le n<m and $m$ is prime, j-i is not divisible by $m$.

Also, since $m$ is odd, $2$ has an inverse modulo $m$.

Therefore, the subsegment sum is divisible by $m$ if and only if

2x+i+j-1 \equiv 0 \pmod m.

Equivalently,

i+j \equiv 1-2x \pmod m.

Now notice that for all pairs 0\le i<j\le n, the value i+j can be equal to every integer from $1$ to 2n-1.

Thus, if

2n-1\ge m,

these values contain representatives of all possible residues modulo $m$. Hence, regardless of the value of $x$, Taras can always find a suitable non-empty subsegment.

On the other hand, if

2n-1<m,

the values 1,2,\ldots,2n-1 do not cover all residues modulo $m$.

Since $m$ is an odd prime, as $x$ varies, the value 1-2x can be any residue modulo $m$. Therefore, Andrii can choose $x$ such that 1-2x is not represented among 1,2,\ldots,2n-1.

In this case, Taras cannot find a subsegment whose sum is divisible by $m$.

So, in all cases, Taras wins if and only if

2n-1\ge m.

The time complexity of the solution is $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;
}