問題一覧 > 通常問題

No.2517 Right Triangles on Circle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 135
作問者 : MasKoaTS / テスター : Shirotsume fky_
1 ProblemId : 10069 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-10-25 00:28:16

問題文

二次元平面上に NN 個の相異なる点 P1,P2,…,PNP_{1}, P_{2}, \dots, P_{N} があります。点 PiP_{i} (1≤i≤N)(1 \leq i \leq N) の座標は (cos⁡2πAiM,sin⁡2πAiM)\left( \cos \dfrac{2 \pi A_{i} }{M}, \sin \dfrac{2 \pi A_{i} }{M} \right) です。

1≤i<j<k≤N1 \leq i < j < k \leq N を満たす整数の組 (i,j,k)(i,j,k) であって、三角形 PiPjPkP_{i} P_{j} P_{k} が直角三角形となるものの個数を求めてください。

制約

  • 3≤N≤3×1053 \leq N \leq 3 \times 10^{5}

  • N≤M≤109N \leq M \leq 10^{9}

  • 1≤Ai≤M1 \leq A_{i} \leq M (1≤i≤N)(1 \leq i \leq N)

  • Ai≠AjA_{i} \neq A_{j} (1≤i<j≤N)(1 \leq i < j \leq N)

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

NN MM
A1A_{1} A2A_{2} ⋯\cdots ANA_{N}

  • 11 行目には NN と MM がこの順に半角スペース区切りで与えられる

  • 22 行目には A1,A2,…,ANA_{1},A_{2},\dots,A_{N} がこの順に半角スペース区切りで与えられる

出力

答えを 11 行に出力してください。

サンプル

サンプル1
入力
4 6
2 3 4 5
出力
2

44 個の点の座標は、それぞれ P1(−12,32),P2(−1,0),P3(−12,−32),P4(12,−32)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) です。

このとき、条件を満たす整数の組は (i,j,k)=(1,2,4),(1,3,4)(i, j, k) = (1, 2, 4), (1, 3, 4) の 22 個です。

例えば (i,j,k)=(1,2,4)(i, j, k) = (1, 2, 4) のとき、三角形 P1P2P4P_{1} P_{2} P_{4} は ∠P1P2P4=π2\angle P_{1} P_{2} P_{4} = \dfrac{ \pi }{2} を満たす直角三角形となります。

サンプル2
入力
3 5
1 3 5
出力
0

条件を満たす整数の組は 11 個もありません。

サンプル3
入力
10 10
1 2 3 4 5 6 7 8 9 10
出力
40

本サンプルとは関係ありませんが、答えは32bit整数型に収まらない可能性があることに注意してください。

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