简单数论

2024-03-24 20:09:46

~~数学太恶心了~~
心态爆炸

第一部分质数和约数

一些常识

素数无限
$\sum_{1}^{n}\frac{1}{i} = O(logn) $

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

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

欧拉筛

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*b) = \varphi (a) * \varphi (b)$
如果 $a$ $or$ $b$为质数$\varphi (a*b) = \varphi (a) * \varphi (b)$
如果$(a,b) \neq 1$, $\varphi (a*b) = \varphi (a) * 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)$

唯一分解定理

$N = p1^{c1} + p2^{c2}$… $+ pm^{cm}$

gcd / lcm

欧几里得算法辗转相除
ab = gcd(a,b) * lcm(a,b);

ll gcd(ll a,ll b)
{
    if(b == 0)return a;
    return gcd(b,a%b);
}

第二部分同余

几条常用性质

$\left ( k,m \right ) = d ,ka\equiv k{a}'mod(\text{mod } m)\Rightarrow a\equiv {a}' (\text{mod } m/d)$
$ax\equiv b(\text{mod } c) \Leftrightarrow ax + by = c$
$a\equiv b(\text{mod } c)\Leftrightarrow c\mid b-a $

裴蜀定理

$ax + by = c;(a,b)|c$

扩展欧几里得

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;
}

gcd(a,b) = gcd(b,a%b)
$ax + by = b{ x} + (a- \left \lfloor \frac{a}{b} \right \rfloor){y}$
继续整理即可。

求逆元

1.费马小定理$a^{p} \equiv 1(\text{mod } p)$,m为质数。
所以a的逆元为$a^{p-2}$;
2.exgcd 求解同余方程$ax \equiv 1(\text{mod } b) 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(中国剩余定理)

$x = b_{i}(\text{mod } a_{i}) $
…………
若$ a_{1} ,a_{2} …… a_{n}$两两互质
$M = \prod_{1}^{n} a_{i}, {m}'_{i} = \frac{M}{a_{i}},t_{i}*{m}'_{i}≡1(\text{mod }a_{i})$
$x= \sum_{1}^{n}b_{i}*{m}'_{i}*t_{i}$
若$ 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^{x} = b(\text{mod }m)$
此处只解决m为质数
将x分解为$i*t - p$
则有$a^{i*t} = b*a^{p}(\text{mod }m)$
$t = \sqrt[2]{m}$时均摊复杂度最小
$ 0< p < t$枚举p 计算出每一个$a^{p}$的值存入hash 再枚举i,算出$a^{i*t}$的值在hash中查找

ll bsgs(ll a,ll b,ll p)
{
    map <ll,ll> hash ;hash.clear();
    ll t = sqrt(p) + 1,j;
    b %= p;
    for(int i = 0 ; i < t ;i++)
    {
        ll tmp = b * qp(a,i,p) % p;
        hash[tmp] = i;
    }
    a = qp(a,t,p);
    if(a == 0)
    {
        if(b == 0)return 1;
        else return -1;
    }
    for(int i = 0 ;i <= t ;i++)
    {
        ll tmp = qp(a,i,p);
        if(hash.find(tmp) == hash.end())
        j = -1;
        else  j = hash[tmp];
        if(i*t-j >=0&&j >= 0)return i*t-j;
    }
    return -1;
    
}