No.1756 Rider's Triangle
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 :
NyaanNyaan
/ テスター :
tokusakurai
PCTprobability
タグ : / 解いたユーザー数 30
作問者 :
NyaanNyaan
/ テスター :
tokusakurai
PCTprobability
問題文最終更新日: 2021-11-20 20:46:44
問題文
非負整数 $a,b (a \leq b)$ に対して、$(a, b)$-rider と呼ばれる変則将棋の駒は次のような動きをすることができる駒です。
- $(x,y)$ に駒があるとき、$0$ でない任意の整数 $i$ に対して $(x+ai,y+bi)$,$(x+bi,y+ai)$,$(x+ai,y-bi)$,$(x+bi,y-ai)$ に駒を動かすことができる。
- ただし、将棋盤の上から $i$ 番目、左から $j$ 番目のマスを $(i,j)$ のように表すものとする。
また、下の図は $13 \times 13$ の将棋盤の $(7,7)$ に $(1,2)$-rider (中央の
R) を置いたもので、$(1,2)$-rider は図の丸印に $1$ 手で動くことができます。
$N \times N$ の将棋盤の上に $3$ 枚の $(a,b)$-rider を、次の条件を満たすように置くことを考えます。
-
$(a,b)$-rider を置く場所を $A, B, C$ （順不同) とする。このとき、
- $A$ にある $(a,b)$-rider を $B$ に $1$ 手で動かすことができる。
- $B$ にある $(a,b)$-rider を $C$ に $1$ 手で動かすことができる。
- $C$ にある $(a,b)$-rider を $A$ に $1$ 手で動かすことができる。
- $A, B, C$ は一直線上に存在しない。
ただし、
- 「一直線上」「三角形の面積」の定義は $A,B,C$ が置かれているマスを直交座標上の点とみなしたときの定義に従います。
- 置き方が異なるとは、片方の置き方ではあるマスに駒が置かれていて、もう片方の置き方ではそうでないようなマスが存在することを言います。
制約
- $0 \leq a \leq b \leq 1000$
- $1 \leq N \leq 10^{18}$
- 入力はすべて整数である。
入力
$a$ $b$ $N$
出力
答えを $1$ 行に出力してください。
サンプル
サンプル1
入力
1 2 20
出力
960
条件を満たす配置のうち三角形の面積が最小になる置き方は $960$ 通りあり、たとえば $A=(1,1), B=(6,11),C= (9,5)$ は条件を満たします。
$A,B,C$ は集合として一致するときは $1$ 通りとして数えることに注意してください。($A= (6, 11), B=(1, 1), C=(9, 5)$ のような置き方は上の例と同一視して考えます。)
サンプル2
入力
1 1 9
出力
0
条件を満たす配置は存在しません。
サンプル3
入力
0 0 9
出力
0
サンプル3
入力
123 456 1000000000
出力
110827630
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。