Divisible or Not#13059

Divisible or Not (Анализа на решението)

Author of the problem:	Andrii Kholod (Connect)
Prepared by:	Andrii Kholod (Connect)
Editorial:	Andrii Kholod (Connect)

Solution

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

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

First, consider the case $m = 2$ m=2.

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

If $n \geq 2$ 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$ m=2, Taras wins if and only if $n \geq 2$ n\ge 2.

Now suppose that $m$ is odd.

If $n \geq m$ 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$ n<m.

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

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

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

Its sum is

$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).

Since $1 \leq j - i \leq n < m$ 1\le j-i\le n<m and $m$ is prime, $j - i$ 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

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

Equivalently,

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

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

Thus, if

$2 n - 1 \geq m,$ 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

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

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

Since $m$ is an odd prime, as $x$ varies, the value $1 - 2 x$ 1-2x can be any residue modulo $m$ . Therefore, Andrii can choose $x$ such that $1 - 2 x$ 1-2x is not represented among $1, 2, \dots, 2 n - 1$ 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

$2 n - 1 \geq m .$ 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;
}

C++