[学习笔记]数论(一)

扩展欧几里得

求二元一次不定方程 $ax+by=gcd(a,b)$ 的一组解。

当 $b=0$ 时，有一组解 $x=1,y=0$ ；

当 $b>0$ 时，因为 $gcd(a,b)=gcd(b,a;mod;b)$ ，

所以设 $x',y'$ 满足 $bx'+(a;mod;b)y'=gcd(a,b)$ ,

则 $bx'+(a-a/b$ imes$b)y'=gcd(a,b)$ ,

整理得 $ay'+b(x'-a/b$ imes$y')=gcd(a,b)$ 。

所以 $x=y',y=x'-a/b$ imes$y'$ 。

就可以在求gcd的过程中得到一组解。

inline int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;y=0;return a;
    }
    else{
        int ret=exgcd(b,a%b,y,x);
        y-=a/b*x;return ret;
    }
}

欧拉函数

欧拉函数 $$phi(x)$ 的定义：小于等于 $x$ 的正整数中与 $x$ 互质的数的个数。

当 $x=1$ 时， $$phi(x)=1$ ；

当 $x>1$ 时， $x$ 可以写成 $k$ 个素数的幂的积的形式,第 $i$ 个素数的质数为 $a_{i}$ :

$x=prod_{i=1}^{k}p_{i}^{a_{i}}$

根据容斥原理得， $phi(x)=x+sum_{Ssubseteq{p_{1},p_{2},dots,p_{k}}}(-1)^{|S|} imes(frac{x}{prod_{p_{i}in;S}p_{i}})$ 。

简单地推一下后发现， $phi(x)=x imesprod_{i=1}^{k}(frac{p_{i}-1}{p_{i}})$ 。

BSGS

求最小的 $x$ 使得 $a^{x}$equiv$b(mod;p),p$ 为质数。

令 $s=sqrt{p}$ ，则 $x=y$ imes$s+r;(0;leq;r<s)$ ，即 $a^{x}=a^{y; imes;s}$ imes$a^{r}$ 。

将所有的 $a^{r}$ 用 $map$ 存起来，从小到大枚举 $y$ ，直到 $b/a^{y; imes;s}$ 是某个 $a^{r}$ ，

此时答案为 $y$ imes$s+r$ 。

$ps:$ 由费马小定理可得， $k^{p-1}$equiv$1(mod;p)$ ，所以 $k^{p-2}$equiv$1/k(mod;p)$ ,

所以可以用快速幂实现除法( $gcd(k,p) ot=1$ 时会有 $bug$ )。

typedef long long ll; 
map<ll,ll> m;
inline ll po(ll x,ll k,ll p){
    ll ret=1;
    while(k){
        if(k&1) ret=ret*x%p;
        x=x*x%p;k>>=1;
    }
    return ret;
}
inline ll bsgs(ll a,ll b,ll p){

if(gcd(a,p)!=1)

        if(b) return -1;
        else return 1;

    ll s=sqrt(p),k=1,x=1,y;
    while(s*s<=p) ++s;
    for(ll i=0;i<s;++i){
        if(!m[k]) m[k]=i;

        k=k*a%p;
    }
    for(ll i=0;i<s;++i){
        y=b*po(x,p-2,p)%p;
        if(m.count(y))
            return i*s+m[y];
        x=x*k%p;
    }
    return -1;
}