https://www.cnblogs.com/Ender32k/p/17582944.html
令 \(c_i={w_1}_i-{w_2}_i\)，相当于找到 \((r,P)\)，满足：
把这个东西写成多项式形式，令 \(f(x)=\sum\limits_{i=0}^nc_ix^i\)，即找到一个 \((r,P)\)，满足 \(P\mid f(r)\)。
由于 \(P\) 的下限较小，考虑随机一个 \(P\in [m,10^6]\)，对于每一个 \(r\in [2,P-2]\)，判定是否满足 \(P\mid f(r)\)。
如果把 \(f(2),f(3),\cdots f(P)\) 看作随机数的话，找不到解的概率为 \((1-\frac{1}{P})^P\sim e^{-1}\ge \frac{1}{3}\)，所以我们期望尝试 \(\alpha=3\) 个 \(P\) 就能找出一个解。其中 \(\alpha\) 为常数。
但是此时对于每一个 \(r\) 单独判断的复杂度是 \(O(\alpha n^2)\) 的，虽然利用任意模数多项式多点求值可以做到 \(O(\alpha n\log^2 n)\)，但是官方题解说：
This is indeed enough to solve the problem, however it is certainly not the simplest, nor the most elegant ?, way to do that.
官方说这个做法既不简单也不优雅。然而官方题解给出了一个十分优雅的做法：
由欧拉定理可知，对于 \(r\in \mathbb{Z},P\in \mathbb{N^*}\)，若 \(\gcd(r,P)=1\)，则 \(r^{\varphi(P)}\equiv 1\pmod P\)。所以存在一个正整数 \(k\) 使得 \(r^k\equiv 1\pmod P\)，称最小的 \(k\) 为 \(\delta_P(r)\)，即 \(k\) 为 \(r\) 在模 \(P\) 意义下的阶。
注意到 \(r^k\equiv r^{k\ \text{mod}\ \delta(r)}\mod P\)，所以令 \(g_{j,\delta(r)}=\sum\limits_{i\equiv j\pmod {\delta(r)}}c_i,0\le j<\delta(r)\)，那么有：
由于 \(g\) 的值只和 \(\delta(r)\) 有关，这启示我们对于某些 \(\delta(r)\mid k\)，算出 \(g_{i,k}\) 的值，然后就可以 \(O(k)\) 地进行求值了。对于 \(k\) 个 \(r\)，我们的多点求值复杂度就变成了 \(O(k^2)\)。而且我们仍认为此时的 \(f(r)\) 是随机的，于是无解的概率为 \((1-\frac{1}{P})^k\)，随机大约 \(\frac{P}{k}\) 次即有 \(\left((1-\frac{1}{P})^k\right)^{\frac{P}{k}}=(1-\frac{1}{P})^P\sim \frac{1}{3}\) 的概率无解，此时再多试几个 \(P\) 即可。
问题转换为给定 \(k,P\)，如何快速求出 \(k\) 个 \(r_1,r_2,\cdots ,r_k\) 满足 \(\forall 1\le i\le k,\delta(r_i)\mid k\)。
首先若 \(\delta(r)\mid k\)，那么显然有 \(\delta(r^\alpha)\mid k\)，\(\alpha\in \mathbb{N^*}\)。
考虑到 \(k\mid (P-1)\)，那么如果存在 \(r^{\frac{P-1}{k}}\not\equiv 1\pmod P\)，由于 \(r^{P-1}\equiv 1\pmod P\)，那么 \(k\) 一定是 \(\delta\left(r^{\frac{P-1}{k}}\right)\) 的倍数。那么令 \(r_1=r^{\frac{P-1}{k}},r_2=r^{\frac{2(P-1)}{k}},\cdots ,r_i=r^{\frac{i(P-1)}{k}}\) 即可。
为了让 \(r_i\) 不重复，\(k\) 取质数即可。此时 \(\delta(r_i)=k\)，需要特判 \(r_1=1\) 或 \(r_1=P-1\) 的情况。
至此，一个基本简单的做法已经成型：
- 枚举 \(k\in \mathbb{P}\)，构造一个质数 \(P\ge m\)，满足 \(k\mid (P-1)\)。
- 在 \(\{1,2,\cdots p-1\}\) 中随机一个 \(r\)，满足 \(r^{\frac{P-1}{k}}\not\equiv 1\pmod P\)。
- 令 \(r_i=r^i\)，对于 \(1\le i\le k\)，\(O(k^2)\) 求出其点值 \(f(r_i)\)，若存在 \(f(r_i)=0\)，\((r_i,P)\) 为合法的答案。
复杂度我不会算，但官方题解说期望尝试 \(O(\log P)\) 次就可以找到想要的解。
// Problem: Heidi Learns Hashing (Hard)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1184A3
// Memory Limit: 250 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
// #if ONLINE_JUDGE
// #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
// #else
#define gh() getchar()
// #endif
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define ins insert
#define era erase
typedef tuple<int, int, int> tu3;
typedef pair<int, int> pi;
inline int rd() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void wr(int x) {
if (x < 0) x = ~(x - 1), pc('-');
if (x > 9) wr(x / 10);
pc(x % 10 + '0');
}
}
using namespace vbzIO;
mt19937 rnd(time(0));
const int N = 1e5 + 100;
const int M = 1e6 + 100;
int n, m, ct, pr[M], vs[M], c[M], s[M];
char s1[N], s2[N];
void init(int lim) {
vs[1] = 1;
for (int i = 2; i <= lim; i++) {
if (!vs[i]) pr[++ct] = i;
for (int j = 1; j <= ct && i * pr[j] <= lim; j++) {
vs[i * pr[j]] = 1;
if (i % pr[j] == 0) break;
}
}
}
int qpow(int p, int q, int P) {
int res = 1;
for (; q; q >>= 1, p = 1ll * p * p % P)
if (q & 1) res = 1ll * res * p % P;
return res;
}
int f(int d, int x, int P) {
int w = 0, b = 1;
for (int i = 0; i < d; i++)
(w += 1ll * b * s[i] % P) %= P,
b = 1ll * b * x % P;
return w;
}
void solve(int d) {
for (int i = 0; i < d; i++) s[i] = 0;
for (int i = 0; i < n; i++) s[i % d] += c[i];
for (int p = (m / d + 1) * d + 1; p <= 1e6; p += d) {
if (vs[p]) continue;
int _r = rnd() % (p - 2) + 1, tp = qpow(_r, (p - 1) / d, p);
while (tp == 1 || tp == p - 1) _r = rnd() % (p - 2) + 1, tp = qpow(_r, (p - 1) / d, p);
_r = tp;
for (int t = 1, r = _r; t <= d; t++, r = 1ll * r * _r % p) {
if (r == 1 || r == p - 1) break;
if (!f(d, r, p)) wr(p), pc(' '), wr(r), pc(' '), exit(0);
}
}
}
int main() {
n = rd(), m = rd(), init(1e6);
scanf("%s%s", s1, s2);
for (int i = 0; i < n; i++) c[i] = s1[i] - s2[i];
for (int i = 2; i <= ct; i++) solve(pr[i]);
return 0;
}