No.1756 Rider's Triangle
タグ : / 解いたユーザー数 22
作問者 :
PCTprobability
Problem Statement
For non-negative integers $a,b (a \leq b)$, the fairy shogi piece called the $(a, b)$-rider is a piece that can move as follows.
- When the piece is at $(x,y)$, for any integer $i$ other than $0$, it can move to $(x+ai,y+bi)$,$(x+bi,y+ai)$,$(x+ai,y-bi)$,$(x+bi,y-ai)$.
- Here, the square in the $i$-th row from the top and the $j$-th column from the left of the shogi board is denoted by $(i,j)$.
The figure below shows a $(1,2)$-rider (the
R in the center) placed at $(7,7)$ on a $13 \times 13$ shogi board; the $(1,2)$-rider can move to the squares marked with circles in the figure in $1$ move.Consider placing $3$ $(a,b)$-riders on an $N \times N$ shogi board so that the following conditions are satisfied.
-
Let $A, B, C$ (in no particular order) be the squares where the $(a,b)$-riders are placed. Then,
- The $(a,b)$-rider at $A$ can move to $B$ in $1$ move.
- The $(a,b)$-rider at $B$ can move to $C$ in $1$ move.
- The $(a,b)$-rider at $C$ can move to $A$ in $1$ move.
- $A, B, C$ do not lie on a straight line.
Here,
- "On a straight line" and "the area of the triangle" follow their definitions when the squares where $A,B,C$ are placed are regarded as points in Cartesian coordinates.
- Two placements are different if there exists a square that has a piece on it in one placement but not in the other.
Constraints
- $0 \leq a \leq b \leq 1000$
- $1 \leq N \leq 10^{18}$
- All inputs are integers.
Input
$a$ $b$ $N$
Output
Print the answer in $1$ line.
Sample
Sample 1
Input
1 2 20
Output
960
Among the placements satisfying the conditions, there are $960$ placements that minimize the area of the triangle; for example, $A=(1,1), B=(6,11),C= (9,5)$ satisfies the conditions.
Note that placements where $A,B,C$ coincide as sets are counted as $1$ placement. (A placement such as $A= (6, 11), B=(1, 1), C=(9, 5)$ is regarded as identical to the example above.)
Sample 2
Input
1 1 9
Output
0
No placement satisfying the conditions exists.
Sample 3
Input
0 0 9
Output
0
Sample 3
Input
123 456 1000000000
Output
110827630
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。