問題一覧 > 通常問題

No.1881 Everything is the same...

レベル : / AI推定難易度 : 3000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 6
作問者 : 37zigen / テスター : PCTprobability 👑 cologne
お気に入りにしたユーザー ProblemId : 7669 / 自分の提出
問題文最終更新日: 2022-03-18 22:23:46
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 336 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。