首页 > 其他分享 >提高组数论速查

提高组数论速查

时间:2022-10-31 19:47:18浏览次数:53  
标签:剩余 uy gcd 数论 bmod 速查 同余 提高 lambda

同余与剩余系

设有整数 \(n_1,n_2,m\) 满足 \(\exist q_1,q_2,r \in \Z,n_1=mq_1+r,n_2=mq_2+r\),则称 \(n_1,n_2\) 模 \(m\) 同余,记作 \(n_1 \equiv n_2 \pmod m\)。

称所有模 \(m\) 同余(设为 \(r\))的 \(n\) 组成的集合为模 \(m\) 的一个剩余类,记作 \(C_r\)。

设有 \(m\) 个整数构成的集合 \(A\) 满足 \(a_1,\dots,a_m\) 模 \(m\) 互不同余(即从每个剩余类中各取一个数),则称 \(A\) 为模 \(m\) 的一个完全剩余系。

容易证明一个满足上面条件的集合至多有 \(m\) 个数。

我们可以再化简一下,只取与 \(m\) 互质的数,这样就得到了模 \(m\) 的一个简化剩余系。简化剩余系的大小为 \(\varphi(m)\)。

欧几里得算法与裴蜀定理

欧几里得算法(辗转相除法):\(\gcd(a,b)=\gcd(b,a\bmod b)(a,b\in\Z)\)。

证:设 \(a=qb+r,\gcd(b,r)=d\)。

由于 \(\gcd(b,a\bmod b)=\gcd(b,r)\),则有 \(d|r,d|b\),则可以推出 \(d|a\),则有 \(d|\gcd(a,b)\)。

设 \(k=\gcd(a,b)\),则 \(k|a-qb=r\),说明 \(k|\gcd(b,r)\)

因此,\(\gcd(a,b)|\gcd(b,a\bmod b),\gcd(b,a\bmod b)|\gcd(a,b) \Rightarrow \gcd(a,b)=\gcd(b,a\bmod b)\)。

裴蜀定理:若有 \(a,b,m\in\Z\)(\(a,b\) 不全为 0),则存在一组解 \(x,y\in\Z\) 使得 \(ax+by=m\) 的充要条件是 \(\gcd(a,b)|m\),且若有解则必有无穷多组解。

证(拓展欧几里得算法):

必要性显然,下证充分性:

不妨假设 \(a,b \ge 0\),因为正负号的不同可以简单地通过 \(x,y\) 的正负性来改变。

同时,只要证明 \(ax+by=\gcd(a,b)\) 即可,因为对 \(x,y\) 扩大若干倍即可得到 \(m\)。

那么两边同时除以 \(\gcd(a,b)\),即 \(a'x+b'y=1\)。

我们在求 \(\gcd(a',b')\) 的时候是怎么做的?后几步单独拿出来看(不妨设此时的两个求公约数的数分别为 \(u,v\)):

\[\gcd(a',b')=\gcd(u,v)=\gcd(v,1)=\gcd(1,0)=1 \]

发现出现了一个 \(u=qv+1\),移项得到 \(u-qv=1\)。那么现在就得到了一组对于 \(u,v\) 的解。

能不能从 \(u,v\) 推到 \(a',b'\) 呢?答案是可以的。

假设我们上一级求的是 \(\gcd(\lambda u+v,u)=\gcd(u,v)\),已知 \(ux_0+vy_0=1\),要求 \((\lambda u+v)x_1+uy_1\) 的解。

构造:取 \(x_1=y_0,y_1=x_0-\lambda y_0\),得到

\[\begin{aligned} &(\lambda u+v)x_1+uy_1 \\ =&(\lambda u+v)y_0+u(x_0-\lambda y_0) \\ =& \lambda uy_0+vy_0+ux_0-\lambda uy_0 \\ =&ux_0+vy_0=1 \end{aligned} \]

逐层推上去即可,这样不仅证明了该定理,还求出了一组解。

有了特解后,其通解为小学奥数内容,这里不再赘述。

标签:剩余,uy,gcd,数论,bmod,速查,同余,提高,lambda
From: https://www.cnblogs.com/Lewis-Li/p/NOIP_NT.html

相关文章

  • SQL查询(提高版--1)
    表名和字段准备工作:表设计:   –1.学生表    Student(s_id,s_name,s_birth,s_sex)–学生编号,学生姓名,出生年月,学生性别    –2.课程表    Cour......
  • Pandas速查手册中文版
    关键缩写和包导入df:任意的PandasDataFrame对象s:任意的PandasSeries对象同时我们需要做如下的引入:importpandasaspdimportnumpyasnp导入数据-pd.read_csv(filename)......
  • 【XSY4350】摆(行列式,数论,杜教筛)
    题面摆题解首先我们将原矩阵写成\(A+B\),其中\(B\)全是\(C\),那么\(A\)的第\(i\)行就只有其倍数处有值,且\(A_{i,i}=1-C,A_{i,j(i|j\landi\neqj)}=-C\)。那么......
  • NOI ONLINE 2022 提高 游记
    Day?甚至没报名,蹭隔壁机房题目。Day1先看了下三道题,感觉T1T2都可做,T3不太好做,于是决定顺序开题。然而被T1卡到心态爆炸,感觉有很多做的方法,但大多数都是假的。深信此题......
  • numpy(ndarray)和tensor(GPU上的numpy)速查
    类型(Types)NumpyPyTorchnp.ndarraytorch.Tensornp.float32torch.float32;torch.floatnp.float64torch.float64;torch.doublenp.floattorch.float1......
  • 【CQOI2017】小Q的表格(数论,分块)
    题意:有一个无限大的整数表格\(f\)满足以下两条法则:\(f(a,b)=f(b,a)\)。\(b\timesf(a,a+b)=(a+b)\timesf(a,b)\)。初始时\(f(a,b)=a\timesb\)。有\(m\)次修改......
  • [NOI Online 2020 #2 提高 B] 子序列问题 (dp+线段树)
    真的是事后诸葛亮,一下考场就知道怎么做了,现在把题解补回来看到这个问题,我第一下想到的就是\(dp\)。如何\(dp\)?设\(dp[i]\)为以\(i\)为右端点的所有子串的答案之和......
  • [NOI Online #3 提高组] 魔法值(矩阵快速幂+各种优化)
    矩阵快速幂相信其他巨佬讲矩阵快速幂的原理和过程都已经很详细了,这里我就着重讲一讲用裸的矩阵快速幂算法之后,如何优化。优化1:优化矩阵乘法这个好几位大佬讲过了,我也不......
  • 打工人必备:浏览器隐藏的4个实用功能,提高工作效率
    使用浏览器这么多年,很多人只是用来上上网、安装扩展,这也太浪费了。其实每一款浏览器都隐藏着一些功能,这些功能非常实用。那么,浏览器都隐藏哪些功能呢,比如下面这些,利用好这......
  • SEO优化技巧:如何提升流量,提高网站点击率
    企业建设网站的目的,就是为了让更多用户点击进来了解我们的产品、服务。网站拥有了点击量,才会有转化率。那么,我们做SEO优化,如何提升网站的流量,提高网站的点击率呢?下面本文针......