首页 > 其他分享 >基础数论

基础数论

时间:2023-07-22 16:11:07浏览次数:37  
标签:gcd 数论 dfrac sum 基础 times pmod equiv

Upd on 2023.1.12 添加了整除分块和莫比乌斯反演。
Upd on 2023.7.22 重新排版,添加、删去了一些内容,修改了一些晦涩难懂的描述,开放阅读。

$$\huge\textbf{0x01}\ \large\textbf{数论入门}$$

"质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。"
"合数是指在大于1的整数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。"

试除法

那么,如何判断一个数 \(n\) 是否为质数呢?一种方法是从定义出发。暴力地把 \(2\sim n-1\) 的数都验证一遍,如果可以整除,那么该数为合数。否则为质数。
但是,这样是不优的。考虑优化:因为一个数 \(n\) 至少有一个 \(\le \sqrt{n}\) 的因数,所以每次只需要验证 \(2\sim \sqrt{n}\) 之间的数即可。
证明:如果一个数 \(n\) 只有 \(\sqrt{n}+1\sim n\) 之间的因数,那么 \(n\) 与这个因数的商也是 \(n\) 的因数。这个因数的取值范围是 \(2\sim \sqrt{n}\) 的,与假设矛盾,得证。
时间复杂度:\(O(\sqrt{n})\)

欧几里得算法(辗转相除法)

这种算法可以求得 \(a,b\) 的最大公约数 \(\gcd(a,b)\)。
令 \(a=a'\times\gcd(a,b),b=b'\times\gcd(a,b)\)。
由最大公约数的定义,\(a'\) 和 \(b'\) 显然互质。
可以据此推导出 \(a'-b'\) 和 \(b'\) 互质。
可以得到 \(\gcd(a,b)=\gcd[(a'-b')\times\gcd(a,b),b'\times\gcd(a,b)]=\gcd(a-b,b)\)。
重复上述操作直到不能再减。
此时有 \(\gcd(a,b)=\gcd(a\bmod b,b)\)。

void gcd(int a,int b){//在这里我们默认a>b
        if(a%b==0)return b;//此时gcd(a,b)=b
        return gcd(b,a%b);//(a%b)<b,应该放在第二个参数
}
//可以优化成这样
void gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
}

时间复杂度:\(O(\log n)\)

筛法求素数

筛法可以在 \(\Theta(n)\) 的时间内求出 \(1\sim n\) 中的每个数是否为质数。
最裸的暴力就是对于每个数,暴力枚举把他的所有倍数都筛掉。这样的复杂度是 \(\Theta(\log\log n)\) 的,接近于线性,但是不是最优的。
考虑优化筛的过程使得每个数都会且仅会被它的最小质因数筛掉。这样复杂度就是线性的了。

f[1]=1;
for(int i=2;i<=n;i++){
	if(f[i]==0)
		pr.push_back(i);
	for(int j=0;j<pr.size()&&i*pr[j]<=n;j++){
		f[i*pr[j]]=1;
		if(i%pr[j]==0)
			break;
	}
}

时间复杂度:\(O(n)\)

欧拉函数

定义欧拉函数 \(\varphi (n)=\sum_{i=1}^n[\gcd(i,n)=1]\)。
欧拉函数的值可以通过以下公式直接算出。
若 \(n=b_1^{a_1}b_2^{a_2}\cdots b_m^{a_m}\),则 \(\varphi(n)=n\prod_{i=1}^m(1-\dfrac{1}{b_i})\)。
证明:考虑容斥。\(1\sim n\) 中,和 \(b_1\) 不互质的数有 \(\dfrac{n}{b_1}\) 个,和 \(b_2\) 不互质的数有 \(\dfrac{n}{b_2}\) 个,依此类推。同时和 \(b_1,b_2\) 不互质的数有 \(\dfrac{n}{b_1b_2}\) 个,同时和 \(b_2,b_3\) 不互质的数有 \(\dfrac{n}{b_2b_3}\) 个,等等。据此可以得到通项公式:
\(\varphi(n)=n+\sum_{S\in\{b_i\}}(-1)^{|S|}\dfrac{n}{\prod_{j\in S}j}=n(1+\sum_{S\in\{b_i\}}\dfrac{(-1)^{|S|}}{\prod_{j\in S}j})=n(1+\sum_{S\in\{b_i\}}\prod_{j\in S}(-\dfrac{1}{j}))=n\prod_{i=1}^m(1-\dfrac{1}{b_i})\)。
特别地,可以用线性筛法求出欧拉函数的值,这个会在后文中有所介绍。

欧拉定理

若 \(a ⊥ p\),则有 \(a^{\varphi(p)}\equiv 1\pmod{p}\)。

扩展欧拉定理

\(a^x\equiv a^{x \operatorname{mod} \varphi(n)+\varphi(n)}\pmod{n}\)

费马小定理

若 \(a⊥p\),则 \(a^{p-1}\equiv 1\pmod p\),即 \(a^{p}\equiv p\pmod p\)。

扩展欧几里得算法

这种算法可以求得一组解 \(x,y\) 使得 \(ax+by=\gcd(a,b)\)。
我们设 \(bx'+(a\bmod b)y'=\gcd(b,(a\bmod b))\)。
因为 \(\gcd(a,b)=\gcd(b,(a\bmod b))\),所以 \(ax+by=bx'+(a\bmod b)y'\)。
因为 \(a\bmod b=a-\lfloor\dfrac{a}{b}\rfloor\times b\),
所以 \(ax+by=bx'+(a-\lfloor\dfrac{a}{b}\rfloor\times b)y'\)。
整理得 \(ax+by=ay'+b(x'-\lfloor\dfrac{a}{b}\rfloor\times y')\),
有 \(x=y',y=(x'-\lfloor\dfrac{a}{b}\rfloor\times y')\)。
这样就可以根据 \(x',y'\) 的值求解 \(x,y\) 的值了。

int Exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
	    return a;
    }else{
    	int la=Exgcd(b,a%b,x,y);
    	swap(x,y);
    	y-=(a/b)*x;
    	return la;
    } 
}

乘法逆元

如果 \(ax\equiv 1\pmod{p}\),且\(\gcd(a,p)=1\),则称 \(a\) 关于 \(p\) 的乘法逆元为 \(x\)。
把上面的式子稍微变形得到 \(ax\equiv \gcd(a,p)\pmod{p}\)。
即 \(ax+py=\gcd(a,p)\)。
使用扩展欧几里得算法。
小性质:\(\dfrac{a}{b}\bmod p = a\times inv(b) \bmod p\)。

int inv(int a,int b){
    int x,y;
    int k=Exgcd(a,b,x,y);
    return (x+b)%b;//解可能是负数
}

特殊地,如果模数 \(p\) 为质数,就可以用费马小定理和快速冥求解逆元。

线性递推阶乘逆元

拜谢 cdx 老师
\(i\times \dfrac{1}{i!}\pmod p=\dfrac{1}{(i-1)!}\pmod p\)

Miller-Rabin素数判断

先来证明引理:对于 \(a^2\equiv1\pmod p\),有 \(a\equiv 1\pmod p\) 或 \(a\equiv n-1\pmod p\)。
证明:因为 \(a^2\equiv 1\pmod p\),
有 \(a^2-1\equiv 0\pmod p\)。
可以得到 \((a+1)(a-1)\equiv 0\pmod p\)。
所以有 \(a-1\equiv 0\pmod p\) 或 \(a+1\equiv 0\pmod p\)。
得证。
费马小定理告诉我们,对于素数 \(p\),有 \(a^{p-1}\equiv 1\pmod p\)。
那是否满足 \(\forall a,a^{p-1}\equiv 1\pmod p\) 的 \(p\) 均为质数?有人给出了反例。
尽管这么判是错的,但是可以通过 Miller-Rabin 算法 使得这么判断的出错率降为极小。
要验证 \(p\) 是否为素数,则把 \(p-1\) 分解成 \(2^tk\)的形式。
接着,我们随一个 \(a\),用快速冥算出 \(a^k\pmod p\)。
然后让这个数不断自乘 \(t\) 次。最后得到的结果为 \(a^{2^tk} \pmod p\),即 \(a^{p-1}\pmod p\)。
如果该数不为 \(1\),则 \(p\) 为合数。
这里注意,尽管满足 \(\forall a,a^{p-1}\equiv 1\pmod p\) 的 \(p\) 不一定是质数,但是不满足该性质的 \(p\) 一定不是质数!
在自乘过程中,如果自乘后的数满足 \(\equiv 1\pmod p\),但是原数不满足 \(\equiv 1\pmod p\) 或 \(\equiv n-1\pmod p\),那么该数也是合数。
反之,该数通过了一次测试。
先人的智慧告诉我们,如果一个数通过了一次测试,那么他不是质数的概率是 \(25\%\)。
那么我们随 \(4\) 次,该数不是质数的概率约为 \(0.3\%\)。随 \(6\) 次的话,概率约为 \(0.02\%\)。概率已经很小了。

int ksm(int b,int t,int mod){
	int ret=1;
	while(t){
		if(t&1)ret=(ret*b)%mod;
		b=(b*b)%mod;t>>=1;
	}
	return ret;
}
int test[7]={2,3,7,61,97,101,103};
bool miller_rabin(int p){
	if(p<2)return 0;
	int k=p-1,cnt=0;
	while(!(k&1))k>>=1,cnt++;
	for(int i=0;i<7;i++){
		if(p==test[i])return 1;
		int a=ksm(test[i],k,p),ne;
		for(int j=1;j<=cnt;j++){
			ne=(a*a)%p;
			if(ne==1&&a!=1&&a!=p-1)return 0;
			a=ne;
		}
		if(a!=1)return 0;
	}return 1;
}

时间复杂度为 \(\log^2n\)。

$$\huge\textbf{0x02}\ \large\textbf{中国剩余定理&扩展中国剩余定理}$$

中国剩余定理

个人感觉用处不是特别大。可以直接看扩展中国剩余定理。
求解同余方程

\[\begin{cases}x \equiv b_1 & \pmod{a_1}\\x \equiv b_2 & \pmod{a_2}\\ \vdots\\x \equiv b_m & \pmod{a_m}\end{cases} \]

其中的 \(b_i\) 两两互质
令 \(M=\prod_{i-1}^m b_i,B_i=\dfrac{M}{b_i},t_iB_i\equiv 1\pmod {b_i}\),则有解 \(x=a_iB_it_i\)。

扩展中国剩余定理

求解同余方程

\[\begin{cases}x \equiv b_1 & \pmod{a_1}\\x \equiv b_2 & \pmod{a_2}\\ \vdots\\x \equiv b_m & \pmod{a_m}\end{cases} \]

如果我们已经求出了一个可行的解 \(x_m\),那么 \(x_m+\operatorname{lcm}_{i=1}^{m}i\) 也是可行的。
同样地,如果我们已经求出了满足前 \(k\) 个同余方程的一个解 \(x_k\),那么 \(x_k+\operatorname{lcm}_{i=1}^{k}i\) 也满足前 \(k\) 个同余方程。
现在考虑如何从 \(x_k\) 转移到 \(x_{k+1}\)。
令 \(s=\operatorname{lcm}_{i=1}^{k}\),\(x_{k+1}=x_k+c_k\times s\)。
则有 \(x_k+c_k\times s\equiv b_{k+1}\pmod{a_{k+1}}\)。
移项得 \(c_k\times s+d_k\times a_{k+1}= b_{k+1}-x_k\)。
\(s,a_{k+1}\) 已知,\(c_k,d_k\) 未知,扩展欧几里得。
这样就求出了 \(x_{k+1}=x_k+c_k\times s\)。

$$\huge\textbf{0x03}\ \large\textbf{Dirchlet 卷积与莫比乌斯反演}$$

以下有函数

\[\Large\epsilon (x)=\begin{cases}1&(x=1)\\0&\text{otherwise.}\end{cases},I(x)=1,id(x)=x. \]

整除分块

求 \(\sum_{i=1}^n\lfloor \dfrac{n}{i}\rfloor\)。$ 1\le n\le\bf1\times 10^{14}$。
暴力枚举 \(i\) 肯定就 T 飞了。
我们列表,当 \(n=12\) 时:

\(i=\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\) \(11\) \(12\)
\(\lfloor \dfrac{n}{i}\rfloor=\) \(12\) \(6\) \(4\) \(3\) \(2\) \(2\) \(1\) \(1\) \(1\) \(1\) \(1\) \(1\)

观察到可能有很长一段区间的 \(\lfloor \dfrac{n}{i}\rfloor\) 都是相同的。而且,相同的 \(\lfloor \dfrac{n}{i}\rfloor\) 必定在一个连续的区间内。
这启发我们可以枚举 \(\lfloor \dfrac{n}{i}\rfloor\) 的所有可能的取值,计算出所有数都等于该值的最长的区间,再将该区间一起计入答案,来减小复杂度。
一个区间的左端点肯定是上一个区间的右端点的位置 \(+1\),现在我们要根据左端点求出相应的右端点。
假设我们确定了左端点,左端点的位置为 \(l\),我们要求的右端点的位置为 \(r\)。
设 \(\lfloor\dfrac{n}{l}\rfloor=\lfloor\dfrac{n}{r}\rfloor=k\),\(n=kl+p=kr+p'(0\le p<l,0\le p')\)。
我们想要的是最长区间,也就是说,我们想要 \(r\) 最大。所以,当 \(p'\ge k\) 的时候是一定不优的。
在 \(0\le p'<k\) 的情况下有 \(p'=n \mod k\)。由此可得 \(r=\lfloor\dfrac{n}{k}\rfloor\)。
代入 \(k=\lfloor\dfrac{n}{l}\rfloor\) 得 \(r=\lfloor\dfrac{n}{\lfloor\dfrac{n}{l}\rfloor}\rfloor\)。

for(long long l=1,r;l<=n;l=r+1/*该区间的左端点是上一区间右端点的位置+1*/){
	r=(n/(n/l));//根据 l 确定 r
	ans+=(r-l+1)*(n/l);
}

复杂度证明:
当 \(i\) 取 \(1\sim \sqrt{n}\) 时,\(\lfloor \dfrac{n}{i}\rfloor\) 最多有 \(\sqrt{n}\) 种取值。当 \(i\) 取 \(\sqrt{n}\sim n\) 时,\(\lfloor \dfrac{n}{i}\rfloor\) 的范围为 \(\sqrt{n}\sim 1\),最多有 \(\sqrt{n}\) 种取值。
所以整除分块的复杂度是 \(\sqrt{n}\) 的。

整除分块可以计算下面的式子。

\[\Large\sum_{i=1}^nf(i)\lfloor \dfrac{n}{i}\rfloor \]

因为每一块中的 \(\lfloor \dfrac{n}{i} \rfloor\) 都是相同的,我们只需要在分块时乘上每一块的 \(f_i\) 的和即可。这可以用前缀和等方式维护。详见下方代码。
求 \(\sum_{i=L}^{R}\tau(i)\)。\(1\le L<R\le 2\times 10^9\)。
转化一下可以得到 \(\sum_{i=L}^Ri\lfloor \dfrac{n}{i}\rfloor\)。

for(long long l=1,r;l<=n;l=r+1){
	r=(n/(n/l));
	ans+=(r*(r+1)-l*(l-1))/2*(n/l);
        //本题的前缀和比较特殊,不需要预处理,直接计算即可。
        //1~x的前缀和为x*(x+1)/2。
}

积性函数

如果 \(\forall a ⊥b,f(a\times b)=f(a)\times f(b)\),则函数 \(f(x)\) 为积性函数。
值得一提的是,所有积性函数都可以用线性筛法求出。

Dirchlet 卷积

如果 \(f(x)\) 和 \(g(x)\) 是两个数论函数的话,它们的 Dirchlet 卷积 \(h(x)\) 也是一个数论函数,满足

\[\Large h(x)=\sum_{d|x}f(d)g(\dfrac{x}{d}). \]

记作 \(h=f*g\)。

莫比乌斯函数

莫比乌斯函数 \(\mu (x)\) 的定义通俗来说就是:

  • 如果 \(x=1\),则 \(\mu (x)=1\)。
  • 如果 \(x\) 能被分解成若干个互不相同的素数 \(a_{1..n}\) 的乘积时,\(\mu (x)=(-1)^n\)。即 \(n\) 为奇数时,\(\mu (x)=-1\);\(n\) 为偶数时,\(\mu (x)=1\)。
  • 否则的话,\(\mu (x)=0\)。

举个例子。\(6\) 能被分解成 \(2\times 3\),所以 \(\mu (6)=1\);\(70\) 能被分解成 \(2\times 5\times 7\),所以 \(\mu (70)=-1\);
但是 \(12 = 2\times 2\times 3\) 不能被分解成若干个互不相同的素数的乘积,所以 \(\mu (12)=0\)。
换句话说,如果存在质数 \(d\),使 \(d^2|x\),那么 \(\mu (x)=0\)。

mu[1]=1;//根据定义
for(int i=2;i<=n;i++){
	if(f[i]==0)mu[i]=-1,pr.push_back(i);
        //i为质数,只能被分解成一个质数的乘积,μ(i)=-1;
	for(int j=0;j<pr.size()&&i*pr[j]<=n;j++){
		f[i*pr[j]]=1;
                //标记这个地方不是质数,同线性筛
		if(i%pr[j]==0)break;
                //如果 pr[j] 为 i 的因数,相当于 pr[j]*pr[j] 是 i*pr[j] 的因数,根据定义 μ(i*pr[j])=-1;
                mu[i*pr[j]]=-mu[i];
                //否则的话, i*pr[j] 唯一分解的素数数量比 i 分解的多 1
	}
}

莫比乌斯反演

如果有两个定义在正整数上的函数 \(f(x)\) 和 \(g(x)\),且满足 \(f(x)=\sum_{d|x}g(d)\),则有

\[\Large g(x)=\sum_{d|x}\mu (d)f(\dfrac{x}{d})=\sum_{d|x}\mu (\dfrac{x}{d})f(d) \]

\[\Large g=\mu*f \]

这被称为莫比乌斯反演。
证明在这里

莫比乌斯函数的性质

莫比乌斯函数有以下良好的性质:
性质一:

\[\Large\sum_{d|x}\mu (d)=\epsilon. \]

证明:
对于 \(x=1\),\(\sum_{d|x}\mu (d) = \mu (1) = 1\)。
否则的话,对于唯一分解为 \(x=a_1^{b_1}\times a_2^{b_2}\cdots a_n^{b_n}\) 的数 \(x\) 的因子 \(d\),
若存在一个质因子的系数大于 \(1\),则根据莫比乌斯函数的定义,有 \(\mu (d)=0\)。
否则的话,每个质因子的系数只有 \(0\) 和 \(1\) 两种取值。设有 \(r\) 个系数取值为 \(1\),则有 \(\mu (d) = (-1)^r\)。
因为满足有 \(r\) 个系数取值为 \(1\) 的 \(d\) 的所有可能取值共有 \(\dbinom{n}{r}\) 个,所以所要求的值为

\[\Large\sum_{r=1}^{n}\dbinom{n}{r}\times (-1)^r=\sum_{r=0}^{n}\dbinom{n}{r}\times (-1)^r\times 1^{n-r}. \]

右面的式子可以使用二项式定理化成 \((-1+1)^n\),即为 \(0\)。得证。
这个性质经常用于将判断转为求和,从而降低复杂度。
性质二:对于任意正整数 \(n\),有

\[\Large\sum_{d|n}\dfrac{\mu (d)}{d}=\dfrac{\varphi (n)}{n}. \]

证明:
有一个引理:\(\sum_{d|n}\varphi (d)=n.\)
证明:\(\forall d|n\),令 \(\gcd(a,n)=d(1\le a\le n)\)。则有 \(\gcd(\dfrac{a}{d}, \dfrac{n}{d})=1\)。对于每一个 \(d\),\(\dfrac{n}{d}\) 为定值。由欧拉函数的定义,符合要求的 \(\dfrac{a}{d}\) 的取值有 \(\varphi (\dfrac{n}{d})\) 种。对于所有 \(d\),符合要求的 \(a\) 的取值有 \(\sum_{d|n}\varphi (\dfrac{n}{d})\) 种。所有可能的 \(a\) 的取值只有 \(n\) 种。于是有 \(n=\sum_{d|n}\varphi (\dfrac{n}{d})=\sum_{d|n}\varphi (d)\)。得证。
根据引理,\(id(n)=\sum_{d|n}\varphi(d)\)。则根据莫比乌斯反演,\(\varphi(n)=\sum_{d|n}\mu(d)id(\dfrac{n}{d})\),两边同除 \(n\) 即得证。

$$\huge\textbf{0x04}\ \large\textbf{BSGS}$$

求解 \(a^x\equiv b\pmod{p}\),其中 \(p\) 为质数。

标签:gcd,数论,dfrac,sum,基础,times,pmod,equiv
From: https://www.cnblogs.com/lunatic-unleashed/p/Basic_number_theory.html

相关文章

  • pyhon 基础学习笔记(一)List
    1.有两个索引 2索引的切片L=[1,2,3,4,5,6]L[start:stop:step]如L[1,2,2] 3.列表增加元素L.append(9),L.append([2,3])尾部追加L.extend([1,2,3]) 尾部追加L.insert(3,5)位置3插入5L[2:2]=[8,9] 下标为2的位置插入8,9 3.列表删除元素L.remove(4)删除元素4......
  • Redis基础
    Redis是用C语言开发的一个开源的高性能键值对(key-value)数据库,官方提供测试数据,50个并发执行100000个请求,读的速度是110000次/s,写的速度是81000次/s,且Redis通过提供多种键值数据类型来适应不同场景下的存储需求,目前为止Redis支持的键值数据类型如下:字符串类型string哈希类......
  • css基础-隐藏显示元素
    display:none隐藏元素,不保留位置,文档结构中存在visibility:hidden隐藏元素,仍占有原来位置<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial......
  • css基础-position定位例子-垂直水平居中
    盒子垂直居中,水平居中实现例子<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>Document......
  • 1. 通俗易懂的Redis基础
    通俗易懂的Redis基础教程(基于CentOS7)目录通俗易懂的Redis基础教程(基于CentOS7)1Redis是什么1.1NoSQL概念1.2NoSQL与SQL比较1.3Redis简介1.4Redis特性1.5Redis优势1.6Redis应用场景2Redis安装2.1Redis官网下载2.2解压Redis2.3安装Redis2.4Redis启动2.5查看Redis是否......
  • 多组异常处理基础
    1.常见的内置异常类  1.1Exception1try:2#一些代码3exceptSpecificException:4#处理特定的异常类型5exceptAnotherException:6#处理另一种异常类型7exceptExceptionase:8#捕获其他未处理的异常,并进行适当处理9print(f"捕......
  • 数字电子技术基础预习提纲
    当然,请见下面的计算机专业数字电子技术基础预习提纲示例,使用Markdown格式:计算机专业数字电子技术基础预习提纲1.数字电子技术基础概述数字电子技术的定义与应用领域数制与编码:二进制、十进制、十六进制、BCD码等逻辑门与布尔代数基础2.组合逻辑电路组合逻辑电路的基本......
  • css基础-position定位
    static静态定位类似于标准流relative相对定位元素移动位置参照原来位置来移动的保留原来的位置(人走了,位置留着,停职留薪),不脱标absolute绝对定位元素移动位置参照父元素如果父元素和父父级等无定位,则以浏览器位置偏移如果父元素有定位,则以父元素为参照进行偏移如果父元素无定位,父......
  • Linux 网络基础 2 三次握手 三次挥手 多进程 多线程服务器
    1.包裹函数对服务器客户端等函数进行报错处理以及简化处理比如bindinttcp4bind(shortport,constchar*IP){structsockaddr_inserv_addr;intlfd=Socket(AF_INET,SOCK_STREAM,0);bzero(&serv_addr,sizeof(serv_addr));if(IP==NULL){//......
  • 异常基础
    1.什么是异常跟java异常(Exception)一样,都是指在程序执行过程中发生的错误或异常情况。当程序出现异常时,会中断正常的执行流程,并转而执行异常处理的逻辑。2.什么情况下触发异常异常可以由多种原因引起,例如:语法错误:代码不符合Python语法规则。运行时错误:在代码执行期间发生了......