問題一覧 > 通常問題

No.984 Inversion

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : tubuann1tubuann1 / テスター : beetbeet
8 ProblemId : 3873 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-02-11 19:01:44

問題文

素数 $P$ と自然数 $N$ が与えられます。
第 $1$ 項から第 $P-1$ 項までの $P-1$ 項からなる数列 $A$ の $i$ 項目の値を次のように定義します。

    $A_i = (i \times N) \% P$
ただし、正の整数 $x,y$ に対して、$x \% y$ は $x$ を $y$ で割った余りを表します。
$P$ 未満の正の整数の組 $(i,j)$ であって、$i\lt j$ かつ $A_i \gt A_j$ をみたすものの数を $2$ で割った余りを求めてください。

入力

$P\ N$

$2 \leq P \leq 2^{31}-1$
$1 \leq N \leq P-1$
$P$ は素数である
入力は全て整数である

出力

答えを一行に出力する。

サンプル

サンプル1
入力
2 1
出力
0

サンプル2
入力
7 3
出力
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。