数论

发表于 更新于

唯一分解定理

n=∏ipiαiνp(i)(n)=αin=\prod_i p_i^{\alpha_i}\\ \nu_{p(i)}(n)=\alpha_i

素数

Fermat 素性检验：检验 an−1≡1(modn)a^{n-1}\equiv 1\pmod n。

二次探测定理：检验 x2≡1(modn)  ⟹  x≡1(modn)∨x≡n−1(modn)x^2\equiv 1\pmod n\implies x\equiv 1\pmod n\lor x\equiv n-1\pmod n。

上述检验若失败则说明 nn 必不是质数。

Miller Rabin

分解 Fermat 素性检验中的指数，n−1=u×2tn-1=u\times 2^t。

对于一个底数 aa，求出 v=au(modn)v=a^u\pmod n。进行至多 tt 次 v←v2v\gets v^2 过程中进行二次探测。

通过所有二次探测后进行 Fermat 素性检验。

Miller Rabin 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
inline ll qmul(ll a,ll b,ll m)
{
    return (ull(a)*b-ull(ld(a)/m*b)*m+m)%m;
}
inline ll qpow(ll x,ll y,ll m)
{
    ll r=1;
    for(;y;x=qmul(x,x,m),y/=2)if(y&1)r=qmul(r,x,m);
    return r;
}
constexpr ll A[7]={2,325,9375,28178,450775,9780504,1795265022};
// constexpr ll A[12]={2,3,5,7,11,13,17,19,23,29,31,37};
inline bool MillerRabin(ll n)
{
    if(n<3||n%2==0)return n==2;
    if(n%3==0)return n==3;
    ll u=n-1,t=0;
    while(u%2==0)u/=2,t++;
    for(int i=0;i<7;i++)
    {
        ll v=qpow(A[i]%n,u,n);
        if(v==0||v==1)continue;
        int s=0;
        for(;s<t;s++)
        {
            if(v==n-1)break;
            v=qmul(v,v,n);
        }
        if(s==t)return false;
    }
    return true;
}

筛

埃氏筛

1
2
3
4
5
6
7
8
std::vector<int> p;
std::bitset<V> np;
for(int i=2;i<=n;i++)if(!np[i])
{
    p.push_back(i);
    if(1ll*i*i>n)continue;
    for(int j=i*i;j<=n;j+=i)np[j]=true;
}

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
std::vector<int> p;
std::bitset<A> np;
for(int i=2;i<=n;i++)
{
    if(!np[i])p.push_back(i);
    for(int j:p)
    {
        if(1ll*i*j>n)break;
        np[i*j]=true;
        if(i%j==0)break;
    }
}

爱用哪个用哪个。级别在 10810^8 以下时埃氏筛可能有常数优势，10910^9 时线性筛更快。

欧几里得算法

若 p=kq+rp=kq+r，则 r=p mod q,k=⌊p/q⌋r=p\bmod q,k=\lfloor p/q\rfloor。

设 a>b,g=gcd⁡(a,b)a>b,g=\gcd(a,b)，则 g∣a,g∣bg\mid a,g\mid b，即 g∣(a−kb)g\mid (a-kb)，g∣a mod bg\mid a\bmod b。

可得 gcd⁡(a,b)=gcd⁡(b,a−b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a-b)=\gcd(b,a\bmod b)。

1
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}

裴蜀定理

∃x,y∈Z,ax+by=gcd⁡(a,b)\exists x,y\in\mathbb{Z},ax+by=\gcd(a,b)。

显然可以在欧几里得算法过程中构造。

设 a=kb+r,gcd⁡(a,b)=bx+rya=kb+r,\gcd(a,b)=bx+ry，则 gcd⁡(a,b)=bx+(a−kb)y=ay+(x−ky)b\gcd(a,b)=bx+(a-kb)y=ay+(x-ky)b。

即 x′=y,y′=x−kyx'=y,y'=x-ky。

exCRT

为了求解线性同余方程 ax≡b(modm)ax\equiv b\pmod m，通过 exgcd 求解 gcd⁡(a,m)=ax′+my′\gcd(a,m)=ax'+my'。

可得

ax′bgcd⁡(a,m)+my′bgcd⁡(a,m)=ba\frac{x'b}{\gcd(a,m)}+m\frac{y'b}{\gcd(a,m)}=b

这样我们就解出了一个特解。发现若 x0x_0 是一个解，那么 x0+kmgcd⁡(a,m)x_0+k\dfrac{m}{\gcd(a,m)} 也是一个解。

ax′b+kmgcd⁡(a,m)+my′b−kagcd⁡(a,m)=ba\frac{x'b+km}{\gcd(a,m)}+m\frac{y'b-ka}{\gcd(a,m)}=b\\

即 x≡x0(modm/gcd⁡(a,m))x\equiv x_0\pmod{m/\gcd(a,m)}。

那么对于方程组

{a1x≡b1(modm1)a2x≡b2(modm2)⋮anx≡bn(modmn)\begin{cases} a_1x\equiv b_1\pmod{m_1}\\ a_2x\equiv b_2\pmod{m_2}\\ \qquad\vdots\\ a_nx\equiv b_n\pmod{m_n}\\ \end{cases}

解得

{x≡x1(modm1′)x≡x2(modm2′)⋮x≡xn(modmn′)\begin{cases} x\equiv x_1\pmod{m_1'}\\ x\equiv x_2\pmod{m_2'}\\ \qquad\vdots\\ x\equiv x_n\pmod{m_n'}\\ \end{cases}

然后每次合并两个方程。设 x=x1+m1′y1=x2+m2′y2x=x_1+m_1'y_1=x_2+m_2'y_2，可得 m1′y1=x2−x1+m2′y2≡x2−x1(modm2′)m_1'y_1=x_2-x_1+m_2'y_2\equiv x_2-x_1\pmod{m_2'}。解得 y1≡y0(modm2′/gcd⁡(m1′,m2′))y_1\equiv y_0\pmod{m_2'/\gcd(m_1',m_2')}。代回有 x=x1+m1′y1≡x1+m1′y0(modm1′m2′/gcd⁡(m1′,m2′)=lcm⁡(m1′,m2′))x=x_1+m_1'y_1\equiv x_1+m_1'y_0\pmod{m_1'm_2'/\gcd(m_1',m_2')=\operatorname{lcm}(m_1',m_2')}。

CRT

数论分块