問題一覧 > 通常問題

No.2260 Adic Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 158
作問者 : karinohitokarinohito / テスター : sotanishysotanishy
4 ProblemId : 9346 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-07 21:18:03

問題文

 正整数 $n$ に対し、$n$ が素数 $p$ で割り切れる回数を $v_p(n)$ と表します。
より厳密には、正整数 $n$ について、非負整数 $k$ 及び $m\not\equiv 0\mod{p}$ である整数 $m$ の組で、$n=p^km$ が成り立つものが一意的に存在するので、$v_p(n)=k$ と定めます。

素数 $P$ と、全ての値が相異なる長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
$$\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}v_P(|A_i-A_j|)$$
を求めてください。

入力

$N$ $P$
$A_1$ $A_2$ $\dots$ $A_N$

  • $2 \leq N \leq 10^5$
  • $2 \leq P \le 10^9$
  • $P$ は素数
  • $1 \leq A_i \le 10^9$
  • $i\neq j$ ならば $A_i\neq A_j$
  • 入力はすべて整数

出力

最後に改行してください。

サンプル

サンプル1
入力
3 2
1 3 5
出力
4

$v_P(|1-3|)=1$, $v_P(|1-5|)=2$, $v_P(|3-5|)=1$ です。
よって、$1+2+1=4$ を出力してください。

サンプル2
入力
5 5
5 55 555 5555 55555
出力
30

サンプル3
入力
8 3
7023 2800 6599 9703 543 4221 1307 6572
出力
18

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