数论基础之——整除

2024-01-25 20:28:40

数论基础之——整除

一堆基本定义、简单定理不说
埃氏筛、欧拉筛
简单说说欧拉筛。

欧拉筛：

通过不扫描它的重复因子来达到线性。
具体说就是记录一个数的最小质因子。
Code：

flag[1]=1;
for(int i=2;i<=n;i++)
{
    if(!flag[i])
        prime[++num]=i;
    for(int j=1;j<=num&&prime[j]*i<=n;j++)
    {
        flag[i*prime[j]]=1;
        if(i%prime[j]==0)
            break;
    }
}

扩展欧几里得：

欧几里得算法：

\[gcd(a,b)=gcd(b,a\bmod b)\]

证明：

显然（大雾）

扩欧：

为解决一个形如
\[ax+by=c\]
的方程。
根据裴蜀定理，当且仅当
\[gcd(a,b)|c\]
时方程有解。
然后解这个方程。。。
我觉得大概就是：
我们设
\[ax_1+by_1=gcd(a,b)\]
\[bx_2+(a\bmod b) y_2=gcd(b,a\bmod b)\]
根据欧几里得以及\(a\bmod b=a-\lfloor a/b\rfloor\)有
\[ax_1+by_1=bx_2+(a-\lfloor a/b\rfloor)y_2\]
\[ax_1+by_1=ay_2+bx_2-\lfloor a/b\rfloor y_2\]
根据恒等定理(?)得：
\[x1=y2,y1=x2-\lfloor a/b\rfloor *y2\]、
然后我们知道，\(gcd(a,b)|c\)。
那么我们算出\(ax+by=gcd(a,b)\)的答案来之后，只要把他乘上\(c/gcd(a,b)\)就好啦。
反正我知道代码哼唧
Code

void exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1;y = 0;
        return;
    }
    return exgcd(b,a%b,y,x);
    y-=a/b*x;
    //计算ax+by=gcd(a,b)的值
}

Miller_Rabin素性测试：

二次探测定理：

\(p\)是质数，且\(x^2\equiv 1 \pmod p\)
则：\(x\equiv1\pmod p\)或\(x\equiv p-1\pmod p\)，且他的逆定理成立。

证明：

\[\because x^2\equiv 1\pmod p\]
\[\therefore (x+1)(x-1)\equiv 0\pmod p\]
\[\therefore p|(x+1) 或 p|(x-1)\]
\(\therefore\)得证。

欧拉函数：

\(\phi (x)\)表示\(<x\)的数中与\(x\)互质的数的个数。
显然，一个合数的\(\phi\)值很小。

Miller_Rabin算法：

假设我现在要测\(n\)是否是素数，钦定\(n>2\)
随机几个素数\(a\)，对于每一个\(a\)，计算：
\[a^{n-1}\bmod n\]
\[\because n是奇数\]
\[\therefore n-1是偶数\]
将\[a^{n-1}\bmod n\]
分解成\[a^{2^k*t}\bmod n\]
计算时，先算\(a^t\)，然后不停平方，每次用二次探测定理判断他是否是素数。最后算到\(a^{n-1}\)，用费马小定理判断是否是素数。如果\[a^{n-1}\bmod n!\equiv 1\]
那么n一定是合数。
如果\(a^{2^i*t}\equiv 1\pmod n\)符合二次探测定理
而且\(a^{2^{i-1}*t}!\equiv 1\pmod n\)并且\(a^{2^{i-1}*t}!\equiv n-1\pmod n\)那么n就是合数。以上都没判断出来的，就有\(\frac{3}{4}\)的几率是质数了。

证明：

据说可以用欧拉函数证，但我不会证qwq
Code

bool check(int p,ll n)
{
    if(p==n)
        return 1;
    if(quick_pow(p,n-1,n)!=1)
        return 0;
    ll s=0,k=n-1;
    while(!(k&1))
    {
        k>>=1;
        s++;
    }
    ll last=quick_pow(p,k,n);
    for(int i=1;i<=s;i++)
    {
        ll now=last*last%n;
        if(now==1)
            return last==n-1||last==1;
        last=now;
    }
    return 0;
}

等等，还有一件事！

当 \(N<4,759,123,141\)，选取 \(a=2,7,61\) 即可确保算法得出正确结果。
当 \(N<3,825,123,056,546,413,051≈3*10^{18}\)，选取\(a=2,3,5,7,11,13,17,19,23\)即可确保算法得出正确结果。

当 \(N<18,446,744,073,709,551,616=2^{64}\)，选取 \(a=2,3,5,7,11,13,17,19,23,29,31,37\)即可确保算法得出正确结果。

Pollard_Rho质因数分解：

我要把一个很大的数\(n\)分解质因子
看这个，代码长这样：
Code

int f(ll x,ll p)
{
    int c=1;
    return (x*x%p+c)%p;
}
void Pollard_Rho(ll x)
{
    if(Miller_Rabin(x))
        return;
    while(1)
    {
        ll a=rand()%x,v1=a,v2=f(a,x);
        while(v1!=v2)
        {
            ll d=gcd(x,(v2-v1+x)%x);
            if(d>1&&d!=x)
            {
                Pollard_Rho(max(d,x/d));
                Pollard_Rho(min(d,x/d));
                return;
            }
            v1=f(v1,x),v2=f(f(v2,x),x);
        }
    }
}

参考文献：

1.扩展欧几里得
 2.Pollard-pho
3.感谢zzy学长的讲解qwq

码农公寓