No.1881 Everything is the same...
タグ : / 解いたユーザー数 6
作問者 :
37zigen
/ テスター :
PCTprobability
👑 Problem Statement
In the Yuki Country, an arithmetic class is being held for $N$ students who are called the Einsteins of the modern age.
After being taught division in the first period, each student $i$ became unable to distinguish integers that have the same remainder when divided by the integer $A_i$.
From the second period onward, X and Y will take turns teaching multiplication, starting with X.
In each class, the teacher chooses one student $i$, chooses one integer $x$ that is coprime to $A_i$, and teaches it.
As a result, this student becomes unable to distinguish integers that become the same number by multiplying by $x$ some number of times.
It is not allowed to choose an $x$ that does not reduce the pairs of integers that the student can distinguish.
If there is no integer to teach in a class, the students are dismissed, and the teacher in charge is held responsible for the students having become unable to distinguish integers.
If X and Y both act optimally, which of them will be held responsible?
Input
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
$1 \leq N \leq 10^4$
$1 \leq A_i \leq 10^5$
Output
Print X if X is held responsible, and Y if Y is held responsible.
Sample
Sample 1
Input
1 1
Output
X
From the beginning, the student cannot distinguish any integers.
Sample 2
Input
1 8
Output
X
Initially, X can teach any of $3,5,7$. Suppose X teaches $3$ and Y teaches $5$. Then the student becomes unable to distinguish numbers that have the same remainder when divided by $8$ after multiplying by $3^i5^j$ $(i, j\geq 0)$. This means that the numbers $1, 3, 5, 7$ coprime to $8$ all become indistinguishable, and X can no longer teach a class. Even if X initially teaches a different number, X is similarly held responsible in the end.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。