简单数论

wtz2333 · 2019-07-20 23:33:54 · 个人记录

数学太恶心了 心态爆炸

第一部分 质数和约数

一些常识

素数无限

欧拉筛，欧拉函数，欧拉定理

这个东西还是有很多骚操作的。

欧拉筛

void LE(int n){
    memset(flag,1,sizeof flag);
    flag[1] = 0;
    for(int i = 2 ;i <= n; i++)
    {
        if(flag[i] == 1)
        {
            prime[++tot] = i;
            phi[i] = i - 1;
        }
        for(int j = 1 ;j <= tot && i*prime[j]<=n;j++)
        {
            flag[i*prime[j]] = 0;
            if(i%prime[j] == 0)
            {
                phi[i*prime[j]] = phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]] = phi[i]*phi[prime[j]];
        }

    }
}

欧拉函数

如果 (a,b) = 1 , \varphi (a\cdot b) = \varphi (a) \cdot \varphi (b)
如果 a 或 b 为质数 \varphi (a\cdot b) = \varphi (a) \cdot \varphi (b)
如果 (a,b) \neq 1, \varphi (a\cdot b) = \varphi (a) \cdot b

欧拉定理及扩展

如果 (a,m),a^{\varphi (m)} \equiv 1(\text{mod } m)
当 b \geq \varphi(p) 时 a^b \equiv a^{b \text{ mod } \varphi(p) + φ(p)} (\text{mod } p)
当 b < \varphi(p) 时 a^b \equiv a^{b} (\text{mod } p)

唯一分解定理

gcd / lcm

欧几里得算法 辗转相除

裴蜀定理

扩展欧几里得

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b == 0){
        x = 1 ,y = 0;return a;
    }
    ll d = exgcd(b,a%b,x,y);
    ll tmp = x;
    x = y;
    y = tmp - (a/b)*y;
    return d;
}

继续整理即可。

求逆元

1.费马小定理 a^{p} \equiv a(\text{mod } p),p 为质数, 所以 a 的逆元为 a^{p-2};
2.exgcd 求解同余方程 ax \equiv 1(\text{mod } b)\Rightarrow ax + by = 1

1~n的逆元

    inv[0] = inv[1] = 1;
    for(int i = 2 ;i <= n ;i++)
    inv[i] = (p - p/i)*inv[p%i]%p;

a[1] ~a[n]的逆元

    for(int i = 1 ;i <= n ;i++){
        a[i] = readl();
        sum[i] = (sum[i-1] * a[i])%p;
    }
    s[n] = qp(sum[n],p - 2);
    for(int i = n - 1; i >= 1 ;i--)
    s[i] = (s[i+1] * a[i+1])%p;
    sum[i] * s[i]//为逆元

CRT(中国剩余定理)

若 a_{1} ,a_{2} …… a_{n} 两两互质

若 m_{1} ,m_{2} …… m_{n} 两两不互质，则可将方程依次两两合并 为 x≡m_{1}×t_{0}+b_{1}\text{mod }lcm(m_{1},m_{2})) 先求解 t_{0},再带入求 x

    for(int i = 1 ; i < n ;i++){
        r2 = p[i+1],m2 = q[i+1];
        ll a = m1,b = m2,c = r2 - r1;
        ll d = exgcd(a,b,x,y);
        if(c%d){cout<<0;return 0;}
        x = ((x*c/d) + (b/d))%(b/d);
        ll mod = lcm(m2,m1);
        ll x0 = (m1*x + r1 )%mod;
        r1 = x0 ; m1 = mod;if(r1 < 0)r1 += mod;
    }

BSGS

则有a^{i\cdot t} = b\cdot a^{p}(\text{mod }m)