首页 > 其他分享 >数论其一

数论其一

时间：2023-09-05 16:47:56浏览次数：38  
标签：其一 gcd space 数论 ll int equiv mod

一、质数

1.质数的定义：

如果一个正整数无法被除了1和它本身以外的任何自然数整除，那么这个数是质数。否则，这个数是合数。

需要注意的是，1既不是质数也不是合数。

2.埃筛：

2.埃筛：
问题：给定一个正整数 \(n\) ，找到\(1\sim n\)中的所有质数。

思路：我们可以从 \(2\) 开始，从小到大扫描每个数。如果当前的数 \(x\) 是质数，就把它的不超过 \(n\) 的倍数\(2x,3x......\)全部标记为合数。最后所有未被标记的数就是质数。

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

for(int i=2;i<=n;++i)
	if(!vis[i])
		for(int j=i*2;j<=n;j+=i)
			vis[j]=1;

3.欧拉筛：

在埃筛中，一个合数会被多次标记，如6会被2和3分别标记一次。

而欧拉筛运用“每个合数只会被它的最小质因数筛一次”的思想，将时间复杂度降低到了\(O(n)\)

思路：设一个数组\(v\)，\(v[i]\)表示 \(i\) 的最小质因数。将 \(2\sim n\) 扫描一遍。设当前的数是\(i\)：如果\(v[i]=0\)，说明 \(i\) 是质数，令 \(v[i]=i\) ，并统计到答案中。接下来扫描不大于 \(v[i]\) 的每个质数\(p\)，令\(v[i\times p]=p\)

for(int i=2;i<=n;++i){
	if(v[i]==0)
		v[i]=i,ans[++m]=i;
	for(int j=1;j<=m;++j){
		if(ans[j]>v[i]||ans[j]>n/i)
			break;
		v[i*ans[j]]=ans[j];
	}
}

二、同余

1.定义：

如果整数 \(a\) 和整数 \(b\) 除以正整数 \(m\) 的余数相等，那么称 \(a,b\) 模 \(m\) 同余，记为：

\(a\equiv b (mod\space m)\)

2.同余的性质：

(1)反身性：\(a\equiv b(mod\space m) \iff b\equiv a(mod\space m)\)

(2)传递性：\(a\equiv b(mod\space m),b\equiv c(mod\space m) \longrightarrow a\equiv c(mod\space m)\)

(3)可加性：\(a\equiv b(mod\space m),c\equiv d(mod\space m) \longrightarrow a+c\equiv b+d(mod\space m)\)

(4)等幂性：\(a\equiv b(mod\space m) \iff a^n\equiv b^n(mod\space m)\)

(5)可约性：\(ac\equiv bc(mod\space m),gcd(c,m)=1 \iff a\equiv b(mod\space m)\)

3.欧几里得算法与扩展欧几里得算法：

欧几里得算法：

\(\forall a,b\in N,b\neq 0,\)有\(gcd(a,b)=gcd(b,a\%b)\)

证明：

若\(a<b\)，则 \(gcd(b,a\%b)=gcd(b,a)=gcd(a,b)\)

若\(a\leq b\)，不妨设 \(a=kb+r\) ，其中\(0\le r<b\)。显然\(r=a\%b\)。对于\(a,b\)的任意公约数\(d\)，\(\because d|a\)，\(d|kb\)，\(\therefore d|(a-kb)\)，\(d|r\)。因此\(d\)是\(b,r\)的公约数。

对于 \(b,r\) 的任意公约数 \(d\)，也能推出 \(d\) 是 \(a,b\) 的公约数。

因此 \(a,b\) 的公约数集合和 \(b,r\) 的公约数集合相同。所以它们的最大公约数相等。

证毕。

int gcd_(int a,int b){
	if(b==0)
		return a;
	return gcd_(b,a%b);
}

扩展欧几里得算法：

前置知识：裴蜀定理：

\(\forall a,b\in N,\exists x,y\) 使得 \(ax+by=gcd(a,b)\)

证明：

在欧几里得定理的最后一步，即 \(b=0\) 时，显然有一对整数 \(x=1,y=0\)，使得\(a\times 1+0\times 0=gcd(a,0)=a\).

假设存在一对正整数 \(x,y\)，满足 \(bx+(a\%b)y=gcd(b,a\%b)\)。那么这时需要证明存在一对正整数\(x'\) , \(y'\) ,满\(ax'+by'=gcd(a,b)\).

我们把\(bx+(a\%b)y=gcd(b,a\%b)\)拆开，也就是\(bx+(a-b\lfloor\frac{a}{b}\rfloor)y=gcd(b,a\%b)\)

也就是\(ay+b(x-\lfloor\frac{a}{b}\rfloor y))=gcd(b,a\%b)\)。这时，只要令\(x'=y,y'=x-\lfloor\frac{a}{b}\rfloor y\)，就能得到\(ax'+by'=gcd(a,b)\).

证毕。

裴蜀定理的证明，实际上给出了整数\(x,y\)的计算方法。这种计算方法就是扩展欧几里得算法。

对于更为一般的方程\(ax+by=c\),它有解当且仅当\(gcd(a,b)|c\)。我们可以先求出\(ax+by=gcd(a,b)\)的一组解\(x_0,y_0\)，然后令\(x_0,y_0\)，同时乘以\(c/gcd(a,b)\)，就能求得\(ax+by=c\)的一组特解。

那么\(ax+by=c\)的通解就是：

\[x=\frac{c}{gcd(a,b)}x_0+\frac{kb}{gcd(a,b)},y=\frac{c}{gcd(a,b)}y_0- \frac {ka} {gcd(a,b)} \]

void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    int tmp=x;x=y;y=tmp-a/b*y;
}

P1516 青蛙的约会

题目可以转化为 \(x+tm\equiv y+tn(mod\space l)\) ，令\(a=x-y\)，\(b=n-m\)，则 \(at\equiv b(mod\space l)\) 。然后就可以解线性同余方程了。注意负数的情况。

void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    int tmp=x;x=y;y=tmp-a/b*y;
}
signed main(){
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    a=n-m;b=x-y;
    if(a<0)
        a=-a,b=-b;
    if(b<0)
        b=(b+l)%l;
    if(b%__gcd(a,l)!=0){
        printf("Impossible\n");
        return 0;
    }
    exgcd(a,l,t,t1);
    t=b/__gcd(a,l)*t;
    t=(t%(l/__gcd(a,l))+(l/__gcd(a,l)))%(l/__gcd(a,l));
    printf("%lld\n",(t%l+l)%l);
    return 0;
}

4.逆元

如果\(ax\equiv 1(mod\space m)\),且 \(a\) 与 \(m\) 互质，那么 \(x\) 是 \(a\) 的模 \(m\) 乘法逆元

逆元的求法1：扩展欧几里得

我们只要将同余柿子转化成\(a\times x+m\times y=1\)，然后求解方程即可

逆元的求法2：费马小定理

费马小定理：若 \(m\) 是质数，且 \(a,m\) 互质,则 \(a^{m-1}\equiv 1(mod \space m).\)

所以\(a^{m-2}\times a\equiv 1(mod \space m).\) 所以我们要求的 \(x\) 就是\(a^{m-2}\)

注意：这种求法只适用于m是质数的情况。

逆元的求法3：线性算法

首先我们知道：\(1^{-1}≡1(mod\space p)\).

设\(p=ki+r,(1<r<i<p)\)，所以\(ki+r\equiv 0(mod\space p)\)

两边乘以\(i^{-1}r^{-1}\)可得：\(kr^{-1}+i^{-1}\equiv 0 (mod\space p)\)

\(i^{-1}\equiv -kr^{-1} (mod\space p)\)

\(i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor\times (p\space mod\space i)^{-1} (mod\space p)\)

int main(){
	scanf("%d%lld",&n,&P);
	inv[1]=1;
	for(int i=2;i<=n;i++)
		inv[i]=(P-(P/i))*inv[P%i]%P;
	for(int i=1;i<=n;++i)
		printf("%lld\n",inv[i]);
	return 0;
}

5.中国剩余定理和扩展中国剩余定理：

中国剩余定理：

设\(a_1,a_2,...,a_n\),是两两互质的整数，\(a=\Pi_{i=1}^na_i, A_i=a/a_i, t_i\) 是线性同余方程\(A_i t_i\equiv 1(mod\space a_i)\)的一个解。

则对于任意的 \(n\) 个整数\(b_1,b_2,...,b_n,\)方程组

\[\begin{cases}x\equiv b_1(mod\space a_1)\\x\equiv b_2(mod\space a_2)\\...\\x\equiv b_n(mod\space a_n)\end{cases} \]

有整数解，解为$x=\sum_{i=1}^n b_i A_i t_i $

证明：
原方程组可以拆解成为n个方程组：

\[\begin{cases}x_1\equiv b_1(mod\space a_1)\\x_1\equiv 0(mod\space a_2)\\...\\x_1\equiv 0(mod\space a_n)\end{cases} \begin{cases}x_2\equiv 0(mod\space a_1)\\x_2\equiv b_2(mod\space a_2)\\...\\x_2\equiv 0(mod\space a_n)\end{cases} ... \begin{cases}x_n\equiv 0(mod\space a_1)\\x_n\equiv 0(mod\space a_2)\\...\\x_n\equiv b_n(mod\space a_n)\end{cases} \]

即：

\[\begin{cases}x_1\equiv b_1(mod\space a_1)\\x_1\equiv 0(mod\space A_1)\end{cases} \begin{cases}x_2\equiv b_2(mod\space a_2)\\x_2\equiv 0(mod\space A_2)\end{cases} ... \begin{cases}x_n\equiv b_n(mod\space a_n)\\x_n\equiv 0(mod\space A_n)\end{cases} \]

此时原方程组的解为：\(x=\sum_{i=1}^n x_i\)

令\(x_i=A_i k_i\)，则第 \(i\) 个方程组就转化为\(A_i k_i\equiv b_i, (mod\space a_i)\)

由题目可知，\(A_i t_i\equiv 1(mod\space a_i)\)，所以\(k_i=t_i b_i\)

所以\(x_i=A_i t_i b_i\)，所以整个方程组的解就是$x=\sum_{i=1}^nb_i A_i t_i $

证毕。

ll exgcd(ll &x,ll &y,ll a,ll b){
	if(b==0){
		x=1;y=0;return a;
	}		
	ll re=exgcd(x,y,b,a%b);
	ll tmp=x;x=y;y=tmp-a/b*y;
	return re;
}
int main(){
	scanf("%lld",&n);
	s=1;
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&a[i],&b[i]);
		s*=a[i];
	}
	for(int i=1;i<=n;++i){
		exgcd(x,y,s/a[i],a[i]);
		x=s/a[i]*((x+a[i])%a[i])*b[i];
		ans=(ans+x)%s;
	}
	printf("%lld\n",ans);
	return 0;
}

扩展中国剩余定理：

还是求解中国剩余定理的方程组，但不保证\(m_1,m_2,...,m_n\) 两两互质。

我们可以通过合并相邻方程的方式求解。

随便挑出两组方程： \(x\equiv a_i (mod\space m_i),x\equiv a_j (mod \space m_j)\)

我们把它转化为一般形式：\(x+y_i m_i=a_i,x+y_j m_j=a_m\)

也就是：\(a_i-a_j=y_i m_i-y_j m_j\)

其中，只有\(y_i,y_j\) 是未知数，所以可以看做关于\(y_i,y_j\)的二元一次方程。

根据裴蜀定理，如果\(a_i-a_j\)不能整除\(gcd(m_i,m_j)\)，那么方程无解。

假设一组特解是\(y_i=y_1,y_j=y_2\)，那么通解就是：

\[y_i=y_1+\frac{km_j}{gcd(m_i,m_j)},y_j=y_2-\frac{km_i}{gcd(m_i,m_j)} \]

\(x\) 的特解是 \(x_0=a_i-y_1 m_i\)

\(x\) 的通解是

\[x=a_i-(y_1+\frac{km_j}{gcd(m_i,m_j)})m_i \]

也就是 \(x=x_0-k\times lcm(m_i,m_j)\)

也就是\(x\equiv x_0 (mod\space lcm(m_i,m_j))\)

这样，我们就把两个方程合并成了一个方程。不断合并下去，就能求出原方程组的解。

ll mul(ll a,ll b,ll mod){
	ll s=a;a=0;bool ok=0;
	if(b<0)
		b=-b,ok=1;
	while(b){
		if(b&1)
			a=(a+s)%mod;
		s=(s+s)%mod;b>>=1;
	}
	if(ok)
		a=-a;
	return a;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1;y=0;return a;
	}
	ll re=exgcd(b,a%b,x,y);
	ll tmp=x;x=y;y=tmp-y*(a/b);
	return re;
}
ll excrt(){
	ll y1=0,y2=0,x0=0,ans=0;
	for(int i=2;i<=n;++i){
		ans=exgcd(m[1],-m[i],y1,y2);
		ll lcm=m[1]/__gcd(m[1],m[i])*m[i];
		y1=mul(y1,m[1],lcm);
		x0=(a[1]-mul(y1,(a[1]-a[i])/ans,lcm)+lcm)%lcm;
		m[1]=lcm;a[1]=x0;
	}
	return x0;
}
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
		scanf("%lld%lld",&m[i],&a[i]);
	printf("%lld\n",excrt());
	return 0;
}

标签：其一,gcd,space,数论,ll,int,equiv,mod
From： https://www.cnblogs.com/andyl/p/17680058.html

相关文章

  • 数论中一个有趣的小结论
    对于任意奇质数\(p\)，对于任意整数\(k<p-1\)，有$p|\sum_{i=1}{p-1}ik$证明：取\(p\)的原根\(g\)，由简化剩余系的性质知：在\(\modp\)意义下，有\[\{g,2g,\cdots,(p-1)g\}=\{1,2,\cdots,p-1\}\]于是\[\sum_{i=1}^{p-1}i^k\equiv\sum_{i=1}^{p-1}(gi)^k\equiv......
  • 数论
    数论模运算\(a\%b=a-b*floor(\fracab)\)费马小定理\(a^{p-1}\%p=1\)最小公倍数&最大公约数(a,b)表示最大公约数[a,b]表示最小公倍数\((a,b)*[a,b]=ab\)辗转相除if(a%b==0)returnb;elsereturngcd(b,a%b);质数筛法for(inti=2;i<=n;i++)......
  • .Net6.0 Redis操作其一List篇
    今天在写字典表时为了优化就用了redis，然后其中就又用到了redis中的一个LIst添加和读取的操作首先Redis支持五种数据类型：string（字符串），hash（哈希），list（列表），set（集合）及zset(sortedset：有序集合)。今天讲的是其中之一lIst（列表）Redis列表是简单的字符串列表，按照插入顺序排序。你可以添加......
  • 【CF1542C】Strange Function（数论）
    题目大意：#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllmod=1e9+7;lln;lllcm(llx,lly){ returnx/__gcd(x,y)*y;}intmain(){ intT; cin>>T; while(T--){ cin>>n; llans=n%mod; for(lli=1,j=1;n/j......
  • 【1342C】Yet Another Counting Problem（数论）
    题目大意：求有多少\(x(1\lel\lex\ler\le10^{18})\)满足\((x\moda)\modb\neq(x\modb)\moda(1\lea,b\le200)\)，有\(q(1\leq\le500)\)次询问。设答案为\(f(l,r)\)，考虑前缀和\(f(l,r)=f(1,r)-f(1,l-1)\),现在问题在于计算\(f(1,x)(1\lex\le10^{18})\)。我们可以发现规......
  • 基础数论
    质数：在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数合数：在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数约数（因数）：能够将一个数整除的数质因数：能够将一个数整除的质数互质：公约数只有1的两个整数质数质数：在大于1的整数中，如果只包含1和本身两个......
  • 『学习笔记』整除分块（数论分块）
    简述整除分块这个东西听起来不是很抽象，但是我理解起来的确有点抽象（可能因为我太菜了吧）。那就先放张图：其实就是颜色相同的点被分成了一块。如果序列总长度是\(n\)，某一个区间左端点是\(l\)，那么\(r=\lfloor\dfrac{n}{\lfloor\dfrac{n}{l}\rfloor}\rfloor\)。所以整除分......
  • 数论-同余与扩展欧几里得详解(附例题及代码)
    数论-同余与扩展欧几里得详解(附例题及代码)注意:这篇文章的信息量会有一点多，请耐心看完一.同余1.1同余的定义给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(modm)简单来说，对于x,y，若x%p=y%p，即x,y对于p的余数......
  • 【学习笔记】简单数论-高斯消元与线性空间
    友情提示本博客内部分内容因缺乏样例，可能晦涩难懂，建议参考蓝书或者数论小白都能看懂的线性方程组及其解法。线性方程组线性方程组是由\(M\)个\(N\)元一次方程共同构成的。线性方程组的所有系数可以写成一个\(M\)行\(N\)列的系数矩阵，再加上每个方程等号右侧的常数，可......
  • 数论笔祭 - 林学长的第二数学
    林学长讲课笔记极限\(\lim_{x\tox_0}f(x)\)考虑运算法则：一般来说，函数的和差商积的极限等于函数的极限的和差商积。但是例外：\[\lim_{x\to3}\frac{x-3}{x^2-9}\]考虑极限约去\(x-3\)得到：\[\lim_{x\to3}\frac1{x+3}=\frac16\]如果约不掉？但是……......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99