数论




对于这一个知识点的学习,我大概会通过
《ACM国际大学生程序设计竞赛:知识与入门》 以及
lrj的蓝书以及《ACM/ICPC数论及应用》来学习.

素数

素数筛法

艾氏筛法(O(nloglogn))

通常使用艾氏筛法,而艾氏筛法的思想也可用于很多地方.

线性筛法

伪码表述

算法: 线性的素数筛法
输出: 一个集合S,表示1~n以内的素数集合
具体流程:

(1) 将S初始化为{2,…,n}
(2) 维护当前确定的素数的列表L,并初始化为空
(3) 对于 2 到 n 的每一个i

(3.1) 如果当前i∈S,将i加入L
(3.2) 对于L中的每一个元素p

(3.2.1) 若i×p>n,结束循环 (3.2)
(3.2.2) 将i×p移出S
(3.2.3) 如果p整除i,结束循环 (3.2)

代码(1亿数据量1s)

实锤完毕…我的电脑竟然可以存下1亿的数组…

#include<bits/stdc++.h>
#define maxn 100001000
using namespace std;

bool valid[maxn];
int prime[maxn];
/*素数筛法 O(n),对于每个素数只标记一次*/
void getPrime(int n,int &tot,int ans[maxn]){
    memset(valid,true,sizeof(valid));
    for(int i=2;i<=n;++i){
        if(valid[i]){
            tot++;
            ans[tot]=i;
        }
        for(int j=1;((j<=tot) && (i*ans[j]<=n));++j){
            valid[i*ans[j]]=false;
            if(i%ans[j]==0) break;
        }
    }
}

int main(){
    clock_t t1 = clock();
    int tot=0;
    getPrime(100000000,tot,prime);
    clock_t t2 = clock();

    cout<<tot<<endl;
    cout<<prime[5760000]<<endl;
    cout<<"总运行时间为: "<<(double)(t2-t1)/ CLOCKS_PER_SEC<<"s"<<endl;
    return 0;
}

素数估计

如果我们设Pi(x)表示不超过x的素数的个数.可以用

x/lnx对Pi(x)进行估计

不到万不得已别用,误差蛮大的

素数判定(*Miller-Rabin)

朴素的素数判定法是通过枚举从2到n^0.5内所有的整数,看他是否能整除n.时间复杂度为O(n^0.5)

此外有一个基于概率的常数时间的素数判定法

Miller-Rabin素数判定

欧几里得算法

求gcd(a,b),欧几里得的一个结论是

gcd(a,b)=gcd(b,a%b)
求得最后结果即可

gcd性质

 gcd(a,b)=gcd(b,a) (交换律)
gcd(-a,b)=gcd(a,b)
gcd(a,a)=|a|
gcd(a,0)=|a|
gcd(a,1)=1
gcd(a,b)=gcd(b, a mod b)
gcd(a,b)=gcd(b, a-b)
如果有附加的一个自然数m,
则: gcd(ma,mb)=m * gcd(a,b) (分配律)
gcd(a+mb ,b)=gcd(a,b)
如果m是a和b的最大公约数,
则: gcd(a/m ,b/m)=gcd(a,b)/m
在乘法函数中有:
gcd(ab,m)=gcd(a,m) * gcd(b,m)
两个整数的最大公约数主要有两种寻找方法:
* 两数各分解质因数,然后取出同样有的质因数乘起来
*辗转相除法(扩展版)
和最小公倍数(lcm)的关系:
gcd(a, b) * lcm(a, b) = ab
a与b有最大公约数,
两个整数的最大公因子可用于计算两数的最小公倍数,或分数化简成最简分数。
两个整数的最大公因子和最小公倍数中存在分配律:
* gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
* lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))
在坐标里,将点(0, 0)和(a, b)连起来,通过整数坐标的点的数目(除了(0, 0)一点之外)就是gcd(a, b)。

扩展欧几里得

扩展算法可以求出两个整数x和y,使得ax+by=gcd(a,b)。在此前提下|x|+|y|取最小值。
对此证明:
http://blog.csdn.net/qq_20200047/article/details/71159677

即可以证明a和b的最大公约数可以写成a和b的线性表示.

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL gcd(LL a,LL b){
    return b ==0?a:gcd(b,a%b);
}

//求整数x和y,使得ax+by=d,在此前提下|x|+|y|取最小值.
//即使a,b在int范围内,也可能超出int
void exgcd(LL a,LL b,LL &d,LL &x,LL &y){
    if(!b){d=a;x=1;y=0;}
    else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}

int main(){

    return 0;
}

一些性质

记(a,b)为gcd(a,b)

(a,b)=(b,a) 且

(a,b,c)=((a,b),c)=(a,(b,c))

记[a,b]为lcm(a,b)

有同上结论

(a,b)*[a,b]=ab (gcd求lcm的由来)

唯一分解定理

简单说吧,对于任意一个整数,都可以化简成素数次幂乘积的形式.

确定正整数n的正约数个数

由唯一分解定理得到的所有素数的幂可以推出约数个数
设第i个素数的幂为{ai}

count=(a1+1)*(a2+1)*(a3+1)*…*(as+1)

而这玩意也有一个玄学快速分解算法

Pollard’s Rho

因为目前题目出现的概率很低,所以延迟学习,先学其他的.

不定方程

基本概念

变量个数多于方程个数,并且只考虑整数解的方程被称之为不定方程。典型的二元一次不定式形式为ax+by=c,其中a、b、c皆为已知整数,a、b都不为0,x、y为未知数.

性质

我们清楚以上方程的形式相当于前面提到过的扩展欧几里得式.

以下我们用python中的整除 ‘//’ 代表数学记号整除

1.二元一次方程ax+by=c有解的充要条件:

(a,b)//c

并且当(a,b)//c的时候该方程等价于

(a/(a,b))*x+(b/(a,b))*y=(c/(a,b))

2.假设二元一次不定方程ax+by=c有解,并且x0、y0为方程的一组解,则他的所有解可以表示为:

x=x0-(b/(a,b))*t
y=y0+(a/(a,b))*t
t为任意整数

3.不定方程非负解
暂略

同余方程与欧拉定理

同余方程

假设m≠0.若m//(a-b)则称a同余于b模m,记为

a≡b(mod m)

证:

a=rm+d
b=km+d
a-b=(r-k)m mod m = 0

定理1

a≡b(mod m),当且仅当m//(a-b)

定理2

a≡b(mod m),当且仅当存在整数k,使得a=b+km

定理3

同余关系是等价关系,即满足以下三条:

  1. 自反性 a≡a(mod m)
  2. 对称性 a≡b(mod m),b≡a(mod m)
  3. 传递性 a≡b(mod m),b≡c(mod m),则a≡c(mod m)

剩余系

指对于一个正整数n,一个整数集合中的数mod n所得的余数域.

完全剩余系

如果一个整数集合的剩余系包含 1~n-1 所有n可能的余数,则该剩余系被称为完全剩余系,我们简记为 Zn.

比如 Z6={0,1,2,3,4,5}

缩系

指在模n意义下完全剩余系中与n互素的剩余系,简记为Zn*.

Zn的同余等价类

Zn中的每个元素都代表所有与他同余的整数,比如n=5时,Z5中的元素”3″实际上代表了3,3+5,3+10…,所有这些整数除以5的余数都是3.

我们把满足同余关系的所有整数看成一个同余等价类,比如 3,8,13,18 都属于”模5等于3″ 这个同余等价类

关于取余等式 k=a%b 的一些性质

即(a+b)%n等,Zn同于等价类意义下四则运算

加法

(a+b)%n = ((a%n)+(b%n))%n

减法

(a-b)%n = ((a%n)-(b%n)+n)%n

乘法

ab%n=(a%n)(b%n)%n

异或

(a^b)%n=((a%n)^b)%n

Zn意义下的除法(模乘法的逆、逆元)

首先说下用处,通常在大整数 a/b 时,或者 c/d*p/x…但最后结果一定是整数时,并且对ans%n,为了避免中间除法运算,我们会用逆元(刚开始学,只知道这些用途,如有缺漏,欢迎补充).

那么向下进行吧

模乘法的逆:

在某些情况下 Zn中的两个元素a和b满足 Zn意义下 ab=1,即ab≡1(mod n).比如

在 Z15 中,7*13=1

即(7*13)%15=1

在这种情况下,我们称a和b互为乘法的逆,记为 b=a(-1),a=b(-1) [-1代表上标].

这个逆的运算很像”倒数”,因为在剩余系中,模n意义下当a(-1)存在时,”除以”一个数a等价于乘以他的乘法逆a(-1),比如在 Z15 中 7(-1)=13,因此3/7=3*7(-1)=3*13=9

这时我们会产生疑问,3/7甚至不是整数,怎么可能等于9? 请注意:

1 我们是在模n意义下对除法进行运算.
2 剩余系中每个元素对应一个同余等价类, 3/7=9的实际含义是”假定有两个整数a和b,其中a/b是整数,且a和b除以15的余数分别为3和7,则a/b除以15的余数等于 9″

比如a=528,b=22就是一例

除法逆元合理性证明

设我们要求 (a / b) mod p
且 b * k ≡ 1 (mod p),即k为b的逆元

注意这里我们可以用扩展欧几里得求出是否存在k,以及k的值
即 答案为 (a * k) mod p
因为 b * k ≡ 1 (mod p)
则有 b * k = p* x+1
得到 k = (p * x + 1) / b
将 k 代入(a * k) mod p

得到:
(a * (p * x + 1) / b) mod p
=((a * p * x) / b + a / b) mod p
=[((a * p * x) / b) mod p +(a / b)] mod p
=[(p * ((a * x) / b)) mod p +(a / b)] mod p
=(0 + (a / b)) mod p
= (a/b) mod p

定理4

若a,b,c是整数,m是正整数,且 a≡b(mod m) ,则

(1) a+c ≡ b+c(mod m)
(2) a-c ≡ b-c(mod m)
(3) ac ≡ bc(mod m)

定理5

设a,b,c,d为整数,m为正整数,若a≡b(mod m),c≡d(mod m)则(注: 一下定理两边值不一定相等,只是mod m相等):

(1) ax+cy≡bx+dy(mod m) 其中x,y为任意整数,即同余式可以相加
(2) ac≡bd(mod m) 即同余式可以相乘
(3) a^n≡b^n(mod m) 由上面那个可以推得,n>0
(4) f(a)≡f(b)(mod m) 其中f(x)为任一整数系数多项式

定理6

设a,b,c,d为整数,m为正整数,则

(1) 若 a≡b(mod m),且d//m,则a≡b(mod d)
(2) 若 a≡b(mod m),则gcd(a,m)≡gcd(b,m)
(3) a≡b(mod mi)(1<=i<=n)同时成立,当且仅当 a≡b(mod[m1,m2,m3…mn])

定理7

若ac≡bc(mod m),且gcd(c,m)=d,则a≡b(mod m/d)

证:

记 c=dc1,m=dm1,其中c1,m1互素

由 ac≡bc(mod m)
得 m//(ac-bc)
即 dm1//d(a-b)c1
故 m1//(a-b)c1
由下面那个整除的性质,因为 m1,c1 互质
则 m1//(a-b)
得 a≡b(mod m1)
即 a≡b(mod m/d)

整除的性质

若m | nk, 且m与k互素, 则m | n

欧拉函数

以前写过一次:
连接: http://be-sunshine.cn/index.php/2017/11/25/aoj-ntl_1_d-eulers-phi-function/