問題一覧 > 通常問題

No.2517 Right Triangles on Circle

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 139
作問者 : MasKoaTS / テスター : Shirotsume fky_
お気に入りにしたユーザー ProblemId : 10069 / 自分の提出
問題文最終更新日: 2023-10-25 00:28:16
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 410 (順位表) の他の問題:

Problem Statement

There are $N$ distinct points $P_{1}, P_{2}, \dots, P_{N}$ on a two-dimensional plane. The coordinates of point $P_{i}$ $(1 \leq i \leq N)$ are $\left( \cos \dfrac{2 \pi A_{i} }{M}, \sin \dfrac{2 \pi A_{i} }{M} \right)$.

Find the number of integer triples $(i,j,k)$ satisfying $1 \leq i < j < k \leq N$ such that the triangle $P_{i} P_{j} P_{k}$ is a right triangle.

Constraints

  • $3 \leq N \leq 3 \times 10^{5}$

  • $N \leq M \leq 10^{9}$

  • $1 \leq A_{i} \leq M$ $(1 \leq i \leq N)$

  • $A_{i} \neq A_{j}$ $(1 \leq i < j \leq N)$

  • All input values are integers.

Input

The input is given in the following format.

$N$ $M$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
  • Line $1$ contains $N$ and $M$ in this order, separated by a single-byte space.

  • Line $2$ contains $A_{1},A_{2},\dots,A_{N}$ in this order, separated by single-byte spaces.

Output

Print the answer on $1$ line.

Sample

Sample 1
Input
4 6
2 3 4 5
Output
2

The coordinates of the $4$ points are $P_{1} \left( -\dfrac{1}{2}, \dfrac{ \sqrt{3} }{2} \right), P_{2}(-1, 0), P_{3} \left( -\dfrac{1}{2}, -\dfrac{ \sqrt{3} }{2} \right), P_{4}\left( \dfrac{1}{2}, -\dfrac{ \sqrt{3} }{2} \right)$, respectively.

In this case, there are $2$ integer triples satisfying the condition: $(i, j, k) = (1, 2, 4), (1, 3, 4)$.

For example, when $(i, j, k) = (1, 2, 4)$, the triangle $P_{1} P_{2} P_{4}$ is a right triangle satisfying $\angle P_{1} P_{2} P_{4} = \dfrac{ \pi }{2}$.

Sample 2
Input
3 5
1 3 5
Output
0

Not even $1$ integer triple satisfies the condition.

Sample 3
Input
10 10
1 2 3 4 5 6 7 8 9 10
Output
40

Although unrelated to this sample, note that the answer may not fit in a 32-bit integer type.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。