数论进阶
扩展欧几里得算法
裴蜀定理（Bézout's identity）
\(1\) ：对于任意整数 \(a\)，\(b\) ，存在一对整数 \(x\) ，\(y\) ，满足 \(ax+by=GCD(a,b)\) 。
2：对于任意整数 \(a\)，\(b\) ，二元一次不定方程 \(ax+by=c\) 有整数解 \((x,y)\) 当且仅当 \(GCD(a,b)|c\) 。
扩展欧几里得算法（Extended Euclidean algorithm）
首先，我们来回顾一下欧几里得算法：
void gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
扩展欧几里得算法是用于在已知 \(a\)，\(b\) 的情况下求一组解 \(x\)，\(y\) ，使他们之间满足：\(ax+by=GCD(a,b)=d\)。(GCD即最大公约数)。我们要计算的是 \(a\) 和 \(b\) 的最大公约数，并求出 \(x\) 和 \(y\) 使得 \(ax+by=d\)。
此时，我们已经计算出了下一个状态：\(b\) 和 \((a\%b)\) 的最大公约数，并求出了一组 \(x_1,y_1\) 使得：\(bx_1+(a\%b)y_1=d\) 。而相邻状态之间的关系是怎样的呢？
我们知道：\(a\%b=a-\lfloor{a \over b} \rfloor *b\) ，所以有：
\[\begin{align}
d&=b * x_1 +[a-\lfloor {a\over b} \rfloor *b]*y_1\\
&=b*x_1+a*y_1-\lfloor{a\over b}\rfloor * b * y_1\\
&=a*y_1+b*(x_1-\lfloor {a\over b} \rfloor * y_1)\\
\end{align}
\]
所以：\(x=y_1,y=x_1-\lfloor{a\over b}\rfloor *y_1\) 。
特别的：在欧几里得算法执行到最后一步，即 \(b=0\) 时，我们可以得到一对整数 \(x=1,y=0\) ，使得 \(a*1 + 0*0=GCD(a,0)\) 。
由此便可以写出扩展欧几里得的模板(exGCD)，代码如下：
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
if (b==0) {
x=1;
y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return d;
}
线性同余方程
乘法逆元
中国剩余定理
扩展中国剩余定理
原根
BSGS
代码如下：
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
int log_mod(ll a,ll b,ll n) {
if (b==1) return 0;
gp_hash_table<int,int> hash;
int t=ceil(sqrt(n));
ll z=1;
for (int i=0; i<t; i++) {
hash[b*z%n]=i;
z=z*a%n;
}
int now=1;
for (int i=1; i<=t; i++) {
now=now*z%n;
if (hash.find(now)!=hash.end()) {
return i*t-hash[now];
}
}
return -1;
}
高次剩余
很遗憾，这个内容作者在OIWIKI上找到，而百度百科上的内容也不全。
为了学习高次剩余部分的内容，我们先给出一个问题：
求解 \(x^a\equiv b (mod\ p)\)
我们规定：\(p\) 是个质数。
在学习了原根方面的知识后，我们可以得知：p一定存在一个原根，我们假设这个原根为 \(g\) 。因此，对于模 \(p\) 意义下的任意的数 \(x(0\le x <p)\) 有且仅有一个数满足 \(i(0 \le i<p-1)\) 满足 \(x=g^i\) 。
接下来将会列出解决方案。
方案一
我们令 \(x=g^c\) ，由于 \(g\) 是 \(p\) 的原根（而这个 \(g\) 和 \(c\) ，通过之前学习的方法，我们一定可以找到），那么问题将转化为求解 \((g^c)^a \equiv b (\mod p)\) ，我们可以在将其变换，得到：
\[(g^a)^c\equiv b(mod\ p)
\]
于是，这就变成了离散对数的基本模型了，我们可以用 \(BSGS\) 解决这道题，只要在 \(O(\sqrt p)\) 内解出 \(c\) ，这样就可以得到原方程的一个特解 \(x_0\equiv g^c (mod\ p)\)
方案二
仍然令 \(x=g^c\) ，此时，我们在规定 \(b=g^t\) ，于是我们得到：
\[g^{ac}\equiv g^t (mod\ p)
\]
方程两边同时取离散对数后得到：
\[ac\equiv t (mod\ \varphi (p))
\]
而方程中的 \(t\) 可以通过 \(BSGS\) 求解 \(g^t \equiv b (mod\ p)\) 得到，于是这就转化成了一个线性同余方程的问题。这样便可解除一个特解 \(c_0\) ,\(c\) 的所有通解为 \(c_0+k\frac {\varphi(p)} {gcd(a,\varphi(p))}\) ,其中 \(k\) 为整数。
于是 \(x\) 的通解为： \(g^{c_0+k\frac {\varphi(p)} {gcd(a,\varphi(p))}}\) ，而我们要求的是所有在 \([0,p-1]\) 范围内的解，可以将解一个个放进 \(vector\) 中，直到重复（可以用 \(set\) 或者 \(hash\) 来判断重复，这里我们采用的是 \(hash\) 的方法，不了解 hash 的读者可以看这里，但我们的 hash 是直接调用的，而不是手写的）
代码如下：
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
vector<int> extract_mod(int a,int b,int p){
vector<int> res;
int g=find_yg(p);
int c=log_mod(pow_mod(g,a,p),b,p);
if (c==-1) return res;
int x=pow_mod(g,c,p),t=pow_mod(g,(p-1)/gcd(a,p-1),p);
gp_hash_table<int,int> hash;
while(1){
res.push_back(x);
hash[x]=1;
x=(ll)x*t%p;
if (hash[x]==1) break;
}
return res;
}
exBSGS
代码如下：
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
int exgcd(int a,int b,int &x,int &y){
if (b==0){
x=1;
y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return d;
}
int exBGSG(int a,int b,int n){
if (b==1) return 0;
int cnt=0,x,y;
ll w=1;
while(1){
int d=exgcd(a,n,x,y);
if (d==1) break;
if (b%d!=0) return -1;
b/=d;
n/=d;
w=w*a/d%n;
cnt++;
if (b==w) return cnt;
}
exgcd(w,n,x,y);
b=(ll)b*(x%n+n)%n;
a=a%n;
gp_hash_table<int,int> hash;
int t=ceil(sqrt(n));
ll z=1;
for (int i=0;i<t;i++){
hash[b*z%n]=i;
z=z*a%n;
}
int now=1;
for (int i=1;i<=t;i++){
now=now*z%n;
if (hash.find(now)!=hash.end()){
return i*t-hash[now]+cnt;
}
}
return -1;
}
int main(){
return 0;
}
