Visit of the Great

题目描述

The Great Mushroom King descended to the dwarves, but not everyone managed to see him. Only the few chosen ones could see the King.

We know that only $LCM(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1)$ dwarves can see the Great Mushroom King. Numbers $k, l, r$ are chosen by the Great Mushroom King himself in some complicated manner which is unclear to common dwarves.

The dwarven historians decided to document all visits of the Great Mushroom King. For each visit the dwarven historians know three integers $k_i, l_i, r_i$, chosen by the Great Mushroom King for this visit. They also know a prime number $p_i$. Help them to count the remainder of dividing the number of dwarves who can see the King, by number $p_i$, for each visit.

题意概述

给定$t$组$k, l, r, p$，对于每一组求出$LCM(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1) \bmod p$。保证$p$是质数。

数据范围：$1 \le t \le 10^5, \ 1 \le k \le 10^6, \ 0 \le l \le r \le 10^{18}, \ 2 \le p \le 10^9$。

算法分析

可以证明$(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1) \le 2$。证明如下：

令$g=(k^{2^l}+1, k^{2^{l+1}}+1, \ldots, k^{2^r}+1)$

$g \mid k^{2^n}+1 \Leftrightarrow k^{2^n} \equiv -1 \pmod g$

两边同时平方可得$k^{2^{n+1}} \equiv 1 \pmod g \Leftrightarrow g \mid k^{2^{n+1}}-1$

$\because g \mid k^{2^{n+1}}+1$

$\therefore g \le 2$

由此得证。

令$s=\prod_{i=l}^r (k^{2^i}+1)={k^{2^{l+1}}-1 \over k^{2^l}-1} \cdot {k^{2^{l+2}}-1 \over k^{2^{l+1}}-1} \cdots {k^{2^{r+1}}-1 \over k^{2^r}-1}={k^{2^{r+1}}-1 \over k^{2^l}-1}$。根据费马小定理，$x^{p-1} \equiv 1 \pmod p$，可以在$O(\log r)$的时间内求出$s$。如果$k$是奇数，那么答案是${s \over 2^{r-l}} \bmod p$，否则答案就是$s \bmod p$。

还要考虑到两种特殊情况。一种是$p=2$，直接特判即可；另一种是$p \mid k^{2^l}-1$，这就意味着$\forall i \ge l, \ p \mid k^{2^i}-1$，这等价于$\forall i \ge l, \ k^{2^i}+1 \equiv 2 \pmod p$，因此答案是$2^{r-l+1} \bmod p$。

代码

import std.stdio;

long power(long a, long b, long mod) {
  if (b && ! (a % mod)) return 0;
  long ret = 1;
  while (b) {
    if (b & 1) (ret *= a) %= mod;
    (a *= a) %= mod, b >>= 1;
  }
  return ret;
}

long inv(long a, long p) {
  return power(a, p - 2, p);
}

int main() {
  int T; readf(" %d", &T);
  while (T--) {
    long k, l, r, p, q, ans;
    readf(" %d %d %d %d", &k, &l, &r, &p), q = p - 1;
    if (p == 2) {
      if (k & 1) writeln(0); else writeln(1);
      continue;
    }
    ans = (power(k, power(2, l, q) + q, p) + q) % p;
    if (! ans) ans = power(2, r - l + 1, p);
    else ans = (power(k, power(2, r + 1, q) + q, p) + q) * inv(ans, p) % p;
    if (k & 1) (ans *= power((p >> 1) + 1, r - l, p)) %= p;
    writeln(ans);
  }
  return 0;
}