自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:44:25，当前版本为作者最后更新于2023-08-07 10:47:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

D4T1. P8993 [北大集训 2021] 算术

段数太多不方便考虑。从简化情况入手，考虑划分成 $2$ 段，则原数可写为 $b_1b ^ k + b_0$。去掉 $b_i\gets b_i\bmod p$ 对新数模 $p$ 没有影响，所以可以认为新数为 $b_0b - b_1$，它和真正的新数模 $p$ 相同。

考虑题目限制：

1. 若 $b_1b ^ k + b_0 \equiv 0\pmod p$，则 $b_0b - b_1\equiv 0\pmod p$。用加减消元法消去 $b_0$，得 $b_1(b ^ {k + 1} + 1)\equiv 0\pmod p$。因为 $b_1$ 取 $0\sim p - 1$ 任意值都可以，所以总存在 $b_1\perp p$。这说明 $b ^ {k + 1} \equiv -1\pmod p$。
2. 若 $b_1b ^ k + b_0\equiv x\pmod p$，则 $b_0b - b_1\equiv y\pmod p$，其中 $x, y > 0$。化简得 $b_1(b ^ {k + 1} + 1)\equiv xb - y\pmod p$，即 $xb\equiv y\pmod p$。这要求 $1\sim p - 1$ 任意数乘以 $b$ 后不是 $p$ 的倍数。若 $b\perp p$ 显然满足，否则令 $x$ 为 $\frac p {\gcd(b, p)}$ 即为反例。

综上，$b\perp p$ 且 $b ^ {k + 1}\equiv -1\pmod p$。反过来可以证明若满足限制则 $k$ 满足题目要求。

以段数为 $3$ 为例：原数为 $b_2 b ^ {2k} + b_1 b ^ k + b_0$，新数为 $b_0 b ^ 2 - b_1b + b_2$。对于第一条限制，消元得 $b_2 (b ^ {2k + 2} - 1) + b_1(b ^ {k + 2} + b)\equiv 0\pmod p$。而 $b ^ {k + 1} + 1\equiv 0\pmod p$，且 $b ^ {2k + 2} - 1 = (b ^ {k + 1} + 1) (b ^ {k + 1} - 1)$，$b ^ {k + 2} + b = (b ^ {k + 1} + 1) b$。对于第二条限制，消元得 $b_2 (b ^ {2k + 2} - 1) + b_1(b ^ {k + 2} + b) = x b ^ 2 - y$，即要求 $1\sim p - 1$ 任意数乘以 $b ^ 2$ 后不是 $p$ 的倍数。类似地，容易推出等价于 $b\perp p$。

$b\perp p$ 容易判断，考虑 $b ^ {k + 1} \equiv -1\pmod p$ 的限制。

将等式两侧平方，$b ^ {2k + 2} \equiv 1\pmod p$ 是必要条件，而该必要条件等价于 $2k + 2\mid \delta_{p}(b)$，其中 $\delta_p(b)$ 表示 $b$ 在模 $p$ 意义下的阶，简记为 $d$。又因为之前保证了 $b\perp p$，所以 $\delta_p(b)$ 存在。先 $\mathcal{O}(\log ^ 2 p)$ 求出阶（从 $x = \varphi(p)$ 开始每次将 $x$ 除以 $\varphi(p)$ 的某个质因子并检查是否仍有 $b ^ x\equiv 1\pmod p$）。

当 $d$ 是奇数的时候，显然无解 …… 吗？先别急，如果 $p = 2$ 阁下又该如何应对？输出 $1$ 即可。当 $p > 2$ 的时候无解。

当 $d$ 是偶数的时候，首先检查 $b ^ {\frac d 2}\bmod p$ 是否为 $-1$。若否，则无解。否则输出 $\frac d 2 - 1$ …… 吗？先别急，如果 $d = 2$ 阁下又该如何应对？输出 $2$ 即可。

时间复杂度 $\mathcal{O}(\sqrt p + T\log ^ 2 p)$。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ui = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using ull = unsigned long long;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnd(20060130);
int rd(int l, int r) {return rnd() % (r - l + 1) + l;}

constexpr int mod = 998244353;
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
int add(int x, int y) {return x += y, x >= mod && (x -= mod), x;}
char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + \
  fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {
  int x = 0;
  char s = getc();
  while(!isdigit(s)) s = getc();
  while(isdigit(s)) x = x * 10 + s - '0', s = getc();
  return x;
}

#define putc(x) putchar(x)
inline void print(ui x) {
  if(x >= 10) print(x / 10);
  putc(x % 10 + '0');
}

// ---------- templates above ----------

ll mul(ll A, ll B, ll P) {
	ll C = A * B - ll(double(A) * B / P + 0.1) * P;
	return C < 0 ? C + P : C;
}
ll ksm(ll a, ll b, ll p) {
  ll s = 1;
  while(b) {
    if(b & 1) s = mul(s, a, p);
    a = mul(a, a, p), b >>= 1;
  }
  return s;
}


ll T, p, tmp, phi;
vector<ll> w;
void mian() {
  cin >> T >> p;
  phi = tmp = p;
  for(ll i = 2; i * i <= tmp; i++) {
    if(tmp % i) continue;
    while(tmp % i == 0) tmp /= i;
    phi = phi / i * (i - 1);
  }
  if(tmp > 1) phi = phi / tmp * (tmp - 1);
  tmp = phi;
  for(ll i = 2; i * i <= tmp; i++) {
    if(tmp % i) continue;
    while(tmp % i == 0) tmp /= i;
    w.push_back(i);
  }
  if(tmp > 1) w.push_back(tmp);
  while(T--) {
    ll b;
    cin >> b, b %= p;
    if(__gcd(b, p) > 1) {
      cout << "-1\n";
      continue;
    }
    if(p == 2) {
      cout << "1\n";
      continue;
    }
    ll dt = phi;
    for(ll it : w) {
      while(dt % it == 0) {
        if(ksm(b, dt / it, p) == 1) dt /= it;
        else break;
      }
    }
    if(dt & 1) {
      cout << "-1\n";
      continue;
    }
    if(ksm(b, dt / 2, p) != p - 1) {
      cout << "-1\n";
      continue;
    }
    ll ans = dt / 2 - 1;
    if(ans == 0) ans += dt;
    cout << ans << "\n";
  }
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin); 
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T = 1;
  while(T--) mian();
  fprintf(stderr, "%d ms\n", int(1e3 * clock() / CLOCKS_PER_SEC));
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/