ABC293 E問題 Geometric Progression

等比数列の和の公式が使えるか

問題は、 $\sum_{i=0}^{X-1}A^i$ の $\mod M$ を求めよというものです。
これは等比数列の和の公式から $\sum_{i=0}^{X-1} A^i = \frac{A^X-1}{A-1}$ となり、 $\frac{A^X-1}{A-1} \mod M$ を計算すればよいように思えます。
この計算は、 $A^X-1 \mod M$ と $\frac{1}{A-1} \mod M$ を求めて掛け合わせる計算になります。
$\frac{1}{A-1} \mod M$ は $A-1$ の逆元で、
$(A-1) p \equiv 1 \mod M$
を満たす $p$ のことです。これが求められるのは $A-1$ と $M$ が互いに素 (最大公約数が 1) の場合のみです。互いに素でなく最大公約数が $k (k>1)$ の場合、 $(A-1) p \mod M$ は常に $k$ の倍数で、 1 になることがないためです。
そのため、 $A-1$ と $M$ が互いに素の場合は等比数列の和の公式で答えを出すことができますが、互いに素でない場合は公式は使えません。

ダブリングを用いた計算

$\sum_{i=0}^{X-1}A^i$ を計算する場合、 $X \le 10^{12}$ と大きな値になる可能性があるため、ひとつずつ計算しては時間がかかりすぎます。
そこで、項数を倍々にした和を考えます。最初の 1 から $A^{2^n-1}$ までの $2^n$ 項の和を $P(n)$ と表します。
$P\left(n\right)= \sum_{i=0}^{2^n-1}A^i$
ここから $P\left(n+1\right)$ を求めると、
$P\left(n+1\right)= \sum_{i=0}^{2^{(n+1)}-1}A^i = \sum_{i=0}^{2^n-1}A^i+\sum_{i=2^n}^{2^{(n+1)}-1}A^i$
$= \sum_{i=0}^{2^n-1}A^i+ A^{2^n} \sum_{i=0}^{2^{n}-1}A^i =P(n)+A^{2^n} P(n)$
となることから、 $A^{2^n}$ と合わせて $P(n)$ を $n$ が小さいほうから順に計算していくことができます。

ここから $\sum_{i=0}^{X-1}A^i$ を求めるには、例えば $X=14$ のとき次のように計算します。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  A, X, M = readInts()

  n = Int(ceil(log(2,X)))
  AP = zeros(Int64, n+1)

  AP[1] = 1   # A^0 = 1
  p = A       # A^(2^0)


  for i = 1:n
    AP[i+1] = ((p * AP[i])%M + AP[i])%M   # 1 + A + A^2 + ... + A^(2^(i)-1)
    p = (p * p)%M                         # A^(2^i)
  end

  k = X
  q = A
  ans = 0
  for i = 1:n+1
    if k % 2 == 1
      ans = ((q * ans)%M + AP[i])%M
    end
    q = (q * q) % M
    k = div(k,2)
  end

  println(ans)

end  # function solve

# main
solve()