Contents
中国剩余定理
tips
对于模数不为质数的问题进行求解，我们可以将其因式分解为几个互质的数 (例：1e9=5^9\times 2^9)，分别在小模数下应用某些技巧求解 (例：卢卡斯定理，暴力等)，最后通过 CRT 合并答案。
O(1)快速乘
用于解决中间过程的乘法超出 2^{64} 范围。
inline ll mul(ll x, ll y, ll P) {
return (x * y - (ll)((long double)x / P * y) * P + P) % P;
}
普通CRT
要求模数互质
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
typedef long long ll;
ll a[N], b[N];
inline ll mul(ll x, ll y, ll P) {
return (x * y - (ll)((long double)x / P * y) * P + P) % P;
}
void exgcd(ll a, ll b, ll &x, ll &y) {
if (b==0) {
x = 1; y = 0;
}
else {
exgcd(b, a % b, y , x);
y -= a / b * x;
}
}
ll crt(ll *a, ll *b, int k) {
ll ans = 0, lcm = 1, x, y;
for(int i = 1; i <= k; i++) lcm *= b[i];
for(int i = 1; i <= k; i++) {
ll tp = lcm / b[i];
exgcd(tp, b[i], x, y);
x = (x % b[i] + b[i]) % b[i];
//ans = (ans + tp * x * a[i]) % lcm;
ans = (ans + mul(mul(tp, x, lcm), a[i], lcm)) % lcm;
}
return (ans + lcm) % lcm;
}
int main()
{
scanf("%lld%lld%lld", &b[1], &b[2], &b[3]);
scanf("%lld%lld%lld", &a[1], &a[2], &a[3]);
ll ans = crt(a, b, 3); printf("%lld\n", ans);
return 0;
}
EXCRT
模数可以不互质。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
ll ai[N], bi[N];
int n;
inline ll mul(ll x, ll y, ll P) {
return (x * y - (ll)((long double)x / P * y) * P + P) % P;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1; y = 0; return a;
}
ll gcd = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - a / b * y;
return gcd;
}
ll excrt(vector<int> &ai, vector<int> &bi) {
int n = (int)ai.size();
ll x, y;
ll M = bi[0], ans = ai[0];
for (int i = 1; i < n; i++) {
ll a = M, b = bi[i], c = (ai[i] - ans % b + b) % b;
ll gcd = exgcd(a, b, x, y), bg = b / gcd;
if (c % gcd) return -1;
x = mul(x, c / gcd, bg);
ans += x * M;
M *= bg;
ans = (ans % M + M) % M;
}
return ans;
}
int main() {
scanf("%d", &n);
vector<int> a(n), b(n);
for(int i = 0; i < n; i++) {
scanf("%lld", &b[i]);
scanf("%lld", &a[i]);
}
printf("%lld\n", excrt(a, b));
return 0;
}
题目大意：
设字符串 s=s_1s_2\cdots s_n（n 为偶数），定义操作：
\text{shuffle}(s)=s_1s_3\cdots_{n-1}s_2s_4\cdots s_n
给字符串 s 和 t ，问最少经过多少次 \text{shuffle} 后 s 变成了 t。
解题思路：
设：
\begin{aligned}
s&=aabbccdbae\cr t&=aabdccbbae
\end{aligned}
首先把 \text{shuffle} 分解成几个不同的轮换，例如：
\binom{1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10}{1\ 3\ 5\ 7\ 9\ 2\ 4\ 6\ 8\ 10}=(1)(2\ 3\ 5\ 9\ 8\ 6)(4\ 7)(10)
对于每个循环节，我们取出对应的 s 和 t 的子串：
\binom{a}{a}\binom{abcabc}{abcabc}\binom{bd}{db}\binom{e}{e}
将 s 复制一遍得到 ss，我们可以通过 KMP 算法求出 t 在 ss 中第一次出现的位置 x_i 和 s 在 ss 中除了初位置之外第一次出现的位置 y_i（y_i 也是 s 的最短循环节长度）。可知：
ans \bmod x_i\equiv y_i
通过 EXCRT 合并即可得到答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 50;
string s, t;
int n, b[N];
int vis[N];
int nxt[N];
vector<int> x, y;
inline ll mul(ll x, ll y, ll P) {}
ll exgcd(ll a, ll b, ll &x, ll &y) {}
ll excrt(vector<int> &ai, vector<int> &bi) {}
int main() {
cin >> s >> t;
n = (int)s.length();
for (int i = 1; i <= n; i++) {
if (i <= n / 2) b[i] = 2 * i - 1;
else b[i] = 2 * (i - n / 2);
}
nxt[0] = -1;
for (int i = 1; i <= n; i++) if (!vis[i]) {
int cnt = 0, tmp = i;
string ns, nt;
while (!vis[tmp]) {
vis[tmp] = 1; cnt++;
tmp = b[tmp];
ns += s[tmp - 1];
nt += t[tmp - 1];
}
ns += ns;
vector<int> yy;
int lent = (int)nt.length();
for (int ii = 2, j = 0; ii <= lent; ii++) {
while(~j && nt[j+1-1] != nt[ii-1]) j = nxt[j];
nxt[ii] = ++j;
}
int lens = (int)ns.length(), pos = 0, flag = 0;
for (int ii = 1, j = 0; ii <= lens; ii++) {
while (~j && nt[j+1-1] != ns[ii-1]) j = nxt[j];
j++;
if (j == lent) {
pos = ii-lent+1;
flag = 1;
break;
}
}
if (!flag) {
puts("-1"); return 0;
}
int looplen = lent - nxt[lent];
if (cnt % looplen == 0) cnt = looplen;
x.push_back(cnt);
y.push_back(pos - 1);
}
printf("%lld\n", excrt(y, x));
return 0;
}
欧拉定理
普通欧拉定理
若 gcd(a,m)=1，则 a^{\varphi(m)}\equiv 1 \pmod m
扩展欧拉定理
a^b\equiv \begin{cases}
a^{b\bmod \varphi(p)}, &{gcd(a,p)=1}\cr a^b,&{gcd(a,p) \not =1,\ b<\varphi(p)} \cr a^{b\ mod \ \varphi(p)+\varphi(p)}, &{gcd(a,p)\not =1,\ b \geq \varphi(p)}
\end{cases} \pmod p
应用：
欧拉降幂 2019南京网络赛B
题意：
求a^{a^{…^{a}}}\ mod\ m，其中一共有b个a。
分析：
扩展欧拉定理有如下性质：
a^b\equiv \begin{cases}
a^{b\ mod \ \varphi(p)}, &{b<\varphi(p)} \cr a^{b\ mod \ \varphi(p)+\varphi(p)},&{b \geq \varphi(p)}
\end{cases} \pmod p
因此我们可以递归地处理上面层，再处理当前层。需要注意的是，根据上面的性质，如果当前层的数值大于当前层的模数，外面还需要加一个模数。
递归的边界。首先如果模数变为 1，需要分情况讨论：底数不为 0，则外面需要加一个 P，因此返回 1；否则返回 0。其次如果层数为 0，由于模数不为 1，因此直接返回 1。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a, b, m;
int ksm(int a, int b, int P = m) {
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % P) {
if (b & 1) {
ret = 1LL * ret * a % P;
}
}
return ret;
}
int phi(int x) {
int ans = x;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
ans = ans / i * (i - 1);
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) ans = ans / x * (x - 1);
return ans;
}
bool judge(ll a, ll k, ll m) { // 判断a^k>=m是否为真
ll b = a;
for(; k; k--, b = b * a) if(b >= m) return true;
return false;
}
int solve(int base, int lev, int P) {
if(P == 1) return base < P ? 0 : 1;
if(!lev) return 1;
int tmp = solve(base, lev - 1, phi(P));
int ans = ksm(base, tmp, P);
ans += P * (tmp < phi(P) ? judge(base, tmp, P) : 1);
return ans;
}
int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &a, &b, &m);
int ans = solve(a, b, m);
printf("%d\n", ans % m);
}
return 0;
}
BSGS
普通 BSGS
题目大意
已知数 a,b,p，满足p是质数，求满足 a^x\equiv b\bmod p 的最小自然数x。
数据范围：2\le b,n\le p\le 2^{31}
分析：
设 y=\left\lceil\sqrt{p}\right\rceil ，记录下所有的 a^i\cdot b 的值 (i\in[0,y-1]) ，然后看各个 a^{ky} 的值 (k\in[1,y])，如果存在a^{ky}\equiv a^i\cdot b，则 x=ky-i 即为所求。注意要求的是最小自然数 x ，所以对于记录相同的 a^i\cdot b 值，i 越大越好，所以加入 map 的过程中不需要判断。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
unordered_map<int, int> um; // 手写哈希表速度更快，卡常用
int a, p, b;
int gcd(int x, int y)
int ksm(int a, int b, int c)
int ni(int a,int p)
// 这里的c只在exBSBS中用
int bsgs(int a,int b,int p,int c = 1) {
if (b == 1) return 0;
um.clear();
int f = 1, y = ceil(sqrt(p));
for (int i = 0; i < y; i++) {
int fb = 1LL * f * b % p;
um[fb] = i;
f = 1LL * f * a % p;
}
int tmp = f;
f = 1LL * f * c % p;
for (int i = 1; i <= y; i++) {
if (um.count(f)) return i * y - um[f];
f = 1LL * f * tmp % p;
}
return -1;
}
int main() {
while(~scanf("%d%d%d", &p, &a, &b) && (a || p || b)) {
int ans = bsgs(a, b, p);
if(~ans) printf("%d\n",ans);
else printf("no solution\n");
}
return 0;
}
另一种思路：
设 y=\left\lceil\sqrt{p}\right\rceil ，记录下所有的 a^i 的值 (i\in[0,y-1]) ，然后看各个 a^{ky}\cdot b^{-1} 的值 (k\in[1,y])，如果存在a^{ky}\cdot b^{-1}\equiv a^i，则 x=ky-i 即为所求。这种思路的优势在于应对多组相同 a 、不同 b 询问时，可以只预处理一次；缺点是需要知道 b 的逆元，因此在 p 不是质数的 exBSGS 中不能用。
int bsgs(int a, int b, int p) {
if (b == 1) return 0;
um.clear();
int f = 1, y = ceil(sqrt(p));
for(int i = 0; i < y; i++) {
um[f] = i;
f = 1LL * f * a % p;
}
int tmp = f;
f = 1LL * f * ni(b, p) % p;
for (int i = 1; i <= y; i++) {
if(um.count(f)) return i * y - um[f];
f = 1LL * f * tmp % p;
}
return -1;
}
多组数据的处理
问题：
对于相同的 a,p，给至多 1000 个不同的 b，问满足 a^x\equiv b\pmod p 的最小 x。
分析：
将预处理的复杂度均摊到 O(\sqrt{Tp})，单次查询复杂度 O(\frac{p}{\sqrt{Tp}})=O(\sqrt{\frac{p}{T}})，总体查询复杂度 O(T\cdot \sqrt{\frac{p}{T}})=O(\sqrt{Tp})。
核心代码：
const int m = 1000;
int ff, yy;
void init(int a, int p) {
int f = 1, y = ceil(1.0 * p / m);
ff = ksm(a, y, p); yy = y;
for(int i = 0; i < y; i++) {
tb.add(f, i);
f = 1LL * f * a % p;
}
}
int bsgs(int a, int b, int p) {
if (b == 1) return 0;
int f = ff, y = yy, tmp = f;
f = 1LL * f * ni(b, p) % p;
for(int i = 1; i <= m; i++) {
if (tb[f]) return i * y - tb[f];
f = 1LL * f * tmp % p;
}
return -1;
}
例题：
exBSGS
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
static struct HashTable {}tb;
int gcd(int x, int y) // 略...
int ksm(int a, int b, int c) // 略...
int ni(int a,int p) // 略...
int a, p, b;
int bsgs(int a, int b, int p, int c = 1) {
a %= p; b %= p;
if (b == 1 || p == 1) return 0;
if (!a) return b == 0 ? 1 : -1;
if (!b) return a == 0 ? 1 : -1;
tb.clear();
int f = 1, y = ceil(sqrt(p)), tmp;
for(int i = 0; i < y; i++) {
int fb = 1LL * f * b % p, fa = 1LL * f * a % p;
tb.add(fb, i);
f = fa;
}
tmp = f;
f = 1LL * f * c % p;
for(int i = 1; i <= y; i++) {
if(tb.count(f)) return i * y - tb[f];
f = 1LL * f * tmp % p;
}
return -1;
}
int exbsgs(int a, int b, int p) {
int ret = 0, c = 1, d;
while ((d = gcd(a,p)) != 1) {
if (b % d) return -1;
p /= d; b /= d;
c = 1LL * c * (a / d) % p;
ret++;
if (c == b) return ret;
}
d = bsgs(a, b, p, c);
return d == -1 ? -1 : d+ret;
}
int main()
{
while(~scanf("%d%d%d", &a, &p, &b) && (a || p || b)) {
int ans = exbsgs(a, b, p);
if(~ans) printf("%d\n",ans);
else printf("No Solution\n");
}
return 0;
}