Story

📱

家に帰ったmatcharate君は、今日も全世界で有名なSNS "Ratetta~" で Universal という会話機能を使って、フォロワーさんと話しています。

"今日はとある資格試験の勉強をしようと思いまーす！俗にいう、精進ってやつですね！じゃ、やってきまーす！私の独り言がうるさいかもしれないので、その場合は余儀なく退出してもらって大丈夫でーす！"

(1時間後...)

"...うーん、なんか計算合わないな...なんでここ答え $6$ になるんだろう...。計算したら $\frac{24}{5}$ になったし、全然整数にならん...ぱうー..."

(10分後...)

"ちょっと計算しなおしたところ、私は $7-3=5$ としていました。大変申し訳ございませんでした。しっかり答えは $6$ になりました。"

※ノンフィクションです

問題

長さ $N$ の数列 $A$ が与えられます。以下を満たす $(i,j)\ (1\le i\lt j\le N)$ の組はいくつありますか？

• $|(A_i)^x-(A_j)^y|$ の値が $K$ で割り切れるような正整数 $x,y$ が存在する

入力

入力は以下の形式で与えられる。

制約

• $2\le N\le 10^5$
• $2\le K\le 10^6$、$K$ は素数
• $0\le A_i\le 10^{18}$
• 入力はすべて整数

出力

答えを出力せよ。

入出力例

3 5
2 4 5

1

$(i,j)=(1,2)$ について、例えば $(x,y)=(2,3)$ とすると $|2^2-4^3|=|4-64|=60$ より、これは $5$ で割り切ることができます。これ以外に条件を満たす組は存在しません。

7 7
7 7 7 7 7 7 7

21

5 5
101 7 101 12 101

10

もしかしたらmatcharate君は 7^\bm{7}-12^\bm{3}=823543-1728=821815=164363\times \bm{5} となって計算ミスしてしまったのかもしれませんね...？