No.2517 Right Triangles on Circle
タグ : / 解いたユーザー数 139
作問者 :
MasKoaTS
/ テスター :
fky_
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もしくは右上の雲マークをクリックしてアカウントを作成してください。