初等数论小结

摘要

复习一下数论

符号的说明

  1. 符号:当且仅当存在正实数 和实数 ,使得 ,我们就可以认为, .
  2. 符号:当且仅当存在正实数 和实数 ,使得 ,我们就可以认为, . 大 与大 恰好相反,即 .
  3. 符号:大 符号是大 和大 的结合,即 .
  4. 互质符号: ,表示 x,y 互质
  5. 最小公倍数: ,在无混淆意义下可以写作 .
  6. 最大公约数: ,在无混淆意义下可以写作 .
  7. 阶乘符号 表示 .

补充一下质数的定义:是指约数只有 1 和其本身的数。

同余与剩余系

同余是数论中很重要的一个分支。

定义

如果 a 除以 p 的余数与 b 除以 p 的余数相同,我们认为 a 和 b 在模 p 意义下同余,记作

上式含义即 . 有如下推论

完全剩余系

完全剩余系,即是通过对一一系列正整数 后产生的从 0 至(m-1)的完全数系。通常地,完全剩余系在研究数论时很有用。模 m 的完全剩余系是一个集合 ,记作

简化剩余系

在 m 的完全剩余系中与 m 互质的元素构成模 m 的简化剩余系,也称既约剩余系、缩系,记作 . 形式化地说:

显然,

乘法逆元

在本文中的乘法逆元通常指模逆元。在模 m 意义下,当且仅当 时存在 a 的逆元 ,使得 。逆元是唯一的。在模质数 P 的意义下,除了 0 和 P 的倍数之外,任何数都有乘法逆元。

求逆元的方法有很多。

扩欧

因为 ,即 。于是可以使用 EXGCD 算法求解,时间复杂度 .

int inv(int a,int p){
    int b,t;
    int g=exgcd(a,p,b,t);
    if(g!=1)return -1;
    return b;
}

欧拉定理

,根据欧拉定理有 。因此 a 的逆元就是 ,使用快速幂计算即可。特别地,如果 m 是质数,那么 。因此快速幂的算法常用于当模数是质数的情况。

线性递推逆元

即求 的逆元。有关线性求区间逆元的算法通常需要模数为质数。在模 P 意义下(P 为质数),显然

假定已知 ,利用数学归纳法,我们想办法构造 的式子。首先我们让 P 对 k 取模:

这时 的逆元是已知的,因此把 代换一下

这就构造了关于 k 的一个乘积式,两边同时乘 得到

代换回原式得到

但在递推的时侯可能出现负数,因此写成 也可以。

以此递推即可。写成 常数小。

inv[i]=1ll*(P-P/i)*inv[P%i]%P;

线性递推阶乘逆元

即求 的逆元。

在模质数 P 意义下,乘法运算是封闭的。因此 . 所以直接算 的逆元然后倒推回去即可。还有一种方法,就是先线性递推逆元,然后再做阶乘。

int inv[N];
void inv3(int n,int p){//1!-n! p is primeNum
    int fac[N];
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
    inv[n]=ksm(fac[n],p-2,p);
    for(int i=n;i>1;i--)inv[i-1]=inv[i]*i%p;
}

同余方程

回到一开始的同余。接下来我们讨论一下各个基本形态同余方程的求解。

线性同余方程

该方程的求解显然需要分类讨论。

a,m 互质

如果 ,那么 a 在模 m 意义下存在逆元,因此

a,m 不互质

这时令 。如果 ,显然方程无解。

否则 ,那么方程同除以 d 得到

其中 。由于 ,因此该方程的解为

做完了吗?没有! 是在模 意义下的解,不是在模 意义下的解。在模 意义下的解有 个,即

线性同余方程组

多个线性同余方程可以构成线性同余方程组:

中国剩余定理

如果 两两互质的话可以考虑中国剩余定理。令

显然 ,于是令 ,即 意义下的逆元。然后构造解

验证:把 x 代入 的方程,那么除了 ,其他的 都是 的倍数,因此取模后为 0. 剩下的 在模 意义下为 1,于是只剩下了

中国剩余定理可以方便地构造方程的解,但有很大的局限性。

两两合并

考虑一个通用的方法,我们两两合并求解方程组

于是把等式联立得到

于是可以使用扩欧直接求解这个方程,就可以得到 的一个值,于是构造解

证明:对于方程 1 是显然的,对于方程 2,可以把 写成 ,于是也可以验证。

这样两两合并下去就可以了。放一道 LG4777 模板题的代码。这个方法很多人认为是扩展中国剩余定理,但是是个人都看得出来,两两合并的算法与中国剩余定理半喵钱关系没有啊。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long lld;
typedef long double lf;
typedef unsigned long long uld;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
/******************heading******************/

lld mul(lld a,lld b,lld p){// 这个函数貌似目前只支持非负整数
    if(a<=1000000000&&b<=1000000000)return a*b%p;
    lld res=0;
    while(b){
        if(b&1)res=(res+a)%p;
        a=a*2%p,b>>=1;
    }
    return res;
}
lld exgcd(lld a,lld b,lld &x,lld &y){
    if(!b)return x=1,y=0,a;
    lld t=exgcd(b,a%b,y,x);
    return y=y-(a/b)*x,t;
}

int main(){
    lld n,b=0,a=1;//x=0 mod 1
    scanf("%lld",&n);
    FOR(i,1,n){
        lld a1,b1,k,k1;
        scanf("%lld%lld",&a1,&b1);
        // 求解方程 ak-a1k1=b1-b, 只求 k 就够了
        lld g=exgcd(a,a1,k,k1),d=((b1-b)%a1+a1)%a1;
        k=mul(k,d/g,a1);
        // 然后合并方程
        b=b+a*k, a=a/g*a1, b=(b+a)%a;
    }
    printf("%lld\n",(b+a)%a);
    return 0;
}
/*
 * BUG#1: 没有用防溢出乘法
 * BUG#2: 忘删调试信息
 * BUG#3L L55. a=a*a1/g 不等于 a*=a1/g!
 */

指数同余方程

BSGS 算法

我们仍分情况讨论。如果 ,那么根据欧拉定理有 ,因此只需要验证 是否有解即可。显然,直接计算的复杂度是 的,当 p 是质数时复杂度接近 。这里我们介绍 Shank 的 Baby-Step-Giant-Step 算法,也称 BSGS 算法。

虽然 x 是未知量,但是我们一定可以把 x 写成 的形式。现在问题就变成找到合适的 使得

变换一下方程得到

于是我们有这样一个思路,先计算 的值,把他们存在一个 Hash 表中。然后枚举 并计算 ,查询 Hash 表中是否有与之相等的一个键值,找到这个键值对应的 j 就可以求出 x.

现在计算一下复杂度。计算 的复杂度是 的,然后可以 事先计算 ,我们假定查询一次 Hash 表的复杂度是 的。那么枚举 i 的并查询 Hash 表的复杂度是 的,于是总复杂度是

通常 Hash 表的复杂度是常数级别,因此取 ,得到复杂度是

EX-BSGS 算法

不互质?

. 若 ,显然原方程无解;否则两边同时除以

如果 仍不互质就再除,令 。如果 显然无解,否则得到

同理, ,先判断 是否整除,如果整除就继续除下去。

直到 ,那么记 ,于是式子长这样

因为 ,所以易证 .

那么 有逆元,所以 的系数消掉了,可以 BSGS 了。

给一道 BZOJ3239 的代码。测试数据比较水,不保证 exbsgs 的正确性,不过 bsgs 的正确性可以保证

//BZOJ3239
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int exgcd(int a,int b,int &x,int &y){
    if(!b)return x=1,y=0,a;
    int g=exgcd(b,a%b,y,x);
    return y=y-x*(a/b),g;
}
int inv(int a,int p){// 求逆元
    int b,t;
    int g=exgcd(a,p,b,t);
    if(g!=1)return -1;
    return ((b%p)+p)%p;
}
const int SZ=2e6;
struct hash_map{// 哈希表模板
    struct data{int u,v,nex;};
    data e[SZ<<1];
    int h[SZ],cnt;
    int hash(int u){return u%SZ;}
    int & operator[](int u){
        int hu=hash(u);
        for(int i=h[hu];i;i=e[i].nex)if(e[i].u==u)return e[i].v;
        return e[++cnt]=(data){u,-1,h[hu]},h[hu]=cnt,e[cnt].v;
    }
    void init(){cnt=0;memset(h,0,sizeof(h));}
};
int pow(int a,int m,int p){// 快速幂
    int res=1;
    while(m){
        if(m&1)res=(long long)res*a%p;
        a=(long long)a*a%p,m>>=1;
    }
    return res;
}
hash_map h;
int bsgs(int a,int b,int p){
    int t=sqrt(p),cur=b;// 分块大小
    h.init();
    for(int i=0;i<t;i++)h[cur]=i,cur=(long long)cur*a%p;
    cur=pow(a,t,p);
    int tot=1;
    for(int i=0;i<=t;i++){
        if(h[tot]!=-1&&i*t>=h[tot])return i*t-h[tot];
        tot=(long long)tot*cur%p;
    }
    return -1;
}
int exbsgs(int a,int b,int p){
    int g=gcd(a,p),k=0;
    long long cq=1,ia;//a 的分母系数,a 的逆元
    while(g!=1){
        if(b%g)return -1;// 无解
        cq=cq*g%p,k++;// 迭代次数 +1
        b/=g,p/=g,g=gcd(a,p);
    }
    ia=inv(a,p);
    for(int i=1;i<=k;i++)cq=cq*ia%p;// 系数的逆元
    b=b*cq%p;
    return bsgs(a,b,p)+k;
}
signed main(){
    int a,b,p;
    while(~scanf("%d%d%d",&p,&a,&b)){
        int ans=exbsgs(a,b,p);
        if(ans==-1)puts("no solution");
        else printf("%d\n",ans);
    }
    return 0;
}

大整数乘法

对于两个整型数的乘法可以转化为长整型完成。但对于两个长整型的乘法就没这么简单了。接下来我们讨论求解

的两种算法。

二进制拆位

很容易想到把其中一个数做二进制的拆位,然后一位一位乘上去。事实上这个算法与快速幂的算法极其类似:

lld mul(lld a,lld b,lld p){// 这个函数貌似目前只支持非负整数
    a%=p,b%=p;
    if(a<=1000000000&&b<=1000000000)return a*b%p;
    lld res=0;
    while(b){
        if(b&1)res=(res+a)%p;
        a=a*2%p,b>>=1;
    }
    return res;
}

lld 是自定义的 long long 的别名

直接淦

因为

由于 ,因此 的值一定小于 p,于是可以用 计算这个分式。作差的时侯直接自然溢出。因为两者的差是一定小于 p 的,因此我们只关心低位。这样再调整一下正负性就行了。

lld mul(lld a,lld b,lld p){
    a%=p,b%=p;
    if(a<=1000000000&&b<=1000000000)return a*b%p;
    lld c=(long double)a*b/p, res=a*b-c*p;
    res<0?res+=p:(res>=p?res-=p:0);
    return res;
}

素性检验

即判定一个数是否为素数

以内质数的个数为 . 其中

直接淦

  1. 枚举判断,复杂度 .
  2. 枚举了 以后,就只用枚举之后的奇数了,复杂度 .
  3. 大于等于 5 的质数一定和 6 的倍数相邻。证明:将大于等于 5 的自然数表示为 . 那么 ,则只用判断 . 因此复杂度为 .

上述算法极力减小代码常数但并没有触及算法本身的优化,接下来介绍一些强有力的检验算法。

米勒检验

对于一个正整数 ,设 ,其中 。如果n对b同时满足以下两个条件:

  1. .

称n通过以b为基的米勒检验

显然如果n是质数那么一定通过米勒检验。而如果n是合数又通过了米勒检验,称这些合数为强伪素数。计算表明,通过 为基的最小伪素数是 ,于是我们做素性检验估计做到 就能证明长整型内的数都是素数了。复杂度是 的,其中k是检验次数。放一下核心代码

lld mul(lld a,lld b,lld p){
    a%=p,b%=p;
    if(a<=1000000000&&b<=1000000000)return a*b%p;
    lld c=(Lf)a*b/p, res=a*b-c*p;
    res<0?res+=p:(res>=p?res-=p:0);
    return res;
}
lld pw(lld a,lld m,lld p){//a ^ b mod p
    lld res=1;
    while(m)m&1?res=mul(res,a,p):0,a=mul(a,a,p),m>>=1;
    return res;
}
bool miller_check(lld b,lld n){
    lld t=n-1;
    while(!(t&1))t>>=1;
    if(pw(b,t,n)==1)return 1;//b^t mod n == 1?
    lld p=pw(b,t,n),res=0;
    while(t<n-1)res|=p==n-1, t<<=1, p=mul(p,p,n);
    return p==1&&res;//b^{n-1} mod n == 1?
}
bool miller(lld n){//通过检验就返回1
    if(n==1)return 0;
    const lld base[]={2,3,5,7,11,13,17,19,23},lb=8;
    FOR(i,0,lb){
        if(base[i]==n)return 1;
        else if(n%base[i]==0)return 0;
    }
    FOR(i,0,lb)if(!miller_check(base[i],n))return 0;
    return 1;
}

Pollard-Rho 分解质因数, .,Floyd,Blent 找环算法

整数唯一分解定理

任何正整数都能被唯一表示成一些素数的幂的乘积:

其中 是质数。

Pollard-Rho 算法

讲到整数的分解,自然就要提到大整数的分解算法。朴素的质因数分解是 的试除法。在这里我们介绍大名鼎鼎的波拉德 算法。该算法的思想是通过巧妙的枚举方式来增加分解成功的概率。

Pollard-Rho算法基本在做这样一件事情:随s个小于n的正整数 ,然后随一个 并判定是否满足 。如果满足,那么这个 显然就是一个合法的n的大于1的因子。于是现在问题在于,怎么随?

我们使用一个多项式 来递归生成 序列。具体的说, 直接随一个小于n的正整数,然后

在讨论如何选择 之前,先考虑一下找到 之后的情况。如果找到合法的 使得 ,那么记 ,于是就得到

由于f是一个多项式,因此有

也就是说这形成了一个循环。循环节的长度是 的因数。不过我们不关心循环节的长度,我们关系的是怎么找到同余的两个点。我们这样来枚举:枚举一个k,如果 ,那么一定能推出 . 也就是一个跳一步,一个跳两步,直到他们的差与n的 大于1为止。

还有一个,f一般长啥样?实际应用中,常用 的形式,并且常用种子 .

代码?看板子吧(咕咕)

二次剩余

对于模数 , 整数 , 若存在整数 , 满足 ,则称 是模 意义下的二次剩余,否则是非二次剩余。一个模奇素数 意义下的二次剩余 , 有 个不同的 满足 .

欧拉判别法

对于奇素数 是模 意义下的二次剩余当且仅当

Cipolla 算法

CIpolla 算法用于求具体的 .

首先随机一个 满足 . 期望次数为 2.

,由于不存在,扩域设其为虚根

是一个符合条件的 .

例题 1

给一个大数 n, 问 n 是否是一个完全平方数。 .

随机一些质数判是否存在二次剩余


  转载请注明: Sshwy's Blog 初等数论小结

 上一篇
初探母函数 初探母函数
摘要 本文主要介绍普通母函数及其应用 定义在数学中,某个序列 的母函数(又称生成函数,英语:Generating function)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信
2019.01.26
下一篇 
DP 优化微剖 2 DP 优化微剖 2
引言和《鹰蛋》一样的优化思路 书稿复制 - 问题引入对于长度为 的序列序列 ,要求将其分为 段,使得每一段的和的最大值最小 DP 思路 表示前 个数分 段的最小最大值,记 $S[k]=
2019.01.24
  目录