No.2517 Right Triangles on Circle
タグ : / 解いたユーザー数 134
作問者 :
MasKoaTS
/ テスター :
Shirotsume
fky_
問題文
二次元平面上に $N$ 個の相異なる点 $P_{1}, P_{2}, \dots, P_{N}$ があります。点 $P_{i}$ $(1 \leq i \leq N)$ の座標は $\left( \cos \dfrac{2 \pi A_{i} }{M}, \sin \dfrac{2 \pi A_{i} }{M} \right)$ です。
$1 \leq i < j < k \leq N$ を満たす整数の組 $(i,j,k)$ であって、三角形 $P_{i} P_{j} P_{k}$ が直角三角形となるものの個数を求めてください。
制約
$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)$
入力はすべて整数
入力
入力は次の形式で与えられます。
$N$ $M$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
$1$ 行目には $N$ と $M$ がこの順に半角スペース区切りで与えられる
$2$ 行目には $A_{1},A_{2},\dots,A_{N}$ がこの順に半角スペース区切りで与えられる
出力
答えを $1$ 行に出力してください。
サンプル
サンプル1
入力
4 6 2 3 4 5
出力
2
$4$ 個の点の座標は、それぞれ $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)$ の $2$ 個です。
例えば $(i, j, k) = (1, 2, 4)$ のとき、三角形 $P_{1} P_{2} P_{4}$ は $\angle P_{1} P_{2} P_{4} = \dfrac{ \pi }{2}$ を満たす直角三角形となります。
サンプル2
入力
3 5 1 3 5
出力
0
条件を満たす整数の組は $1$ 個もありません。
サンプル3
入力
10 10 1 2 3 4 5 6 7 8 9 10
出力
40
本サンプルとは関係ありませんが、答えは32bit整数型に収まらない可能性があることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。