問題一覧 > 通常問題

No.1756 Rider's Triangle

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 22
作問者 : NyaanNyaan / テスター : tokusakurai PCTprobability
お気に入りにしたユーザー ProblemId : 7264 / 自分の提出
問題文最終更新日: 2021-11-20 20:46:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 324 (順位表) の他の問題:

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)$.
For example, the $(1,1)$-rider moves in the same way as a bishop, and the $(0,1)$-rider moves in the same way as a rook.
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.
Among the placements satisfying the conditions, letting $(a,b)$-riders be placed at $A, B, C$, find the number of placements for which the area of the triangle formed by $A, B, C$ is minimized, modulo $998244353$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。