当前位置: 首页 > news >正文

数论(未完)

前言:

复习一下数论(部分)

裴蜀定理

结论:

\(∀a,b∈Ζ\),设\(d=gcd(a,b)\) ,则\(∃x,y\)使得\(ax+by=d\)

推论:

  1. \(ax+by=m\)有解,当且仅当\(d|m\)
  2. \(gcd(a,b)=1\),则存在\(x,y\)使得\(ax+by=1\)
  3. 对于\(n\)个数\(a_1,a_1,...a_n\)\(d=gcd\{a_1,a_2,..a_n\}\),则方程$a_1 x_1 + a_2 x_2 + ... +a_n x_n =m $ 有解,当且仅当\(d|m\)

扩展欧几里得(exgcd)

结论:

\(x_0,y_0\)满足\(ax+by=d\),则

\[ \left\{ \begin{matrix}x=x_0-\frac{b}{d}*k\\y=y_0+\frac{a}{d}*k\\ \end{matrix} \right. ~~~~,k∈Ζ\]

\(x,y\)也满足上式,

且这些\(x,y\)是所有可能的解

求解:

\[a ~ mod ~ b ~ = ~ a - \lfloor \frac{a}{b} \rfloor*b \]

\[d=gcd(a,b) =gcd(b,a \% b) = (a - \lfloor \frac{a}{b} \rfloor*b)x+by \]

\[d=ax+b(y-\lfloor \frac{a}{b} \rfloor x) \]

代码:

$code$
inline void exgcd(int a,int b,int &x,int &y){if(!b) x=1,y=0;else exgcd(b,a%b,y,x),y-=a/b*x;
}

应用:

  1. 求逆元
  2. 求解线性同余方程

中国剩余定理(CRT)

自己家的东西还是学学比较好,其实别家的也得学

求解方程

\[ \left\{ \begin{matrix}x ≡ ~ a_1 ~ (~ mod ~ m_1 ~ )\\x ≡ ~ a_2 ~ (~ mod ~ m_2 ~ )\\·\\·\\·\\x ≡ ~ a_n ~ (~ mod ~ m_n ~ ) \end{matrix} \right. \]

求解:

\(m=∏_{i=1}^n m_i,M_i=\frac{m}{m_i},t_i\) 满足 $M_i t_i≡1 ~ (mod ~ m_i) $

\(ans=∑_{i=1}^n a_i M_i t_i\)

证明:

\(M_i=\frac{m}{m_i}\)

\(∀k≠i,M_i t_i ≡ 0 ~ ( ~ mod ~ m_i ~ )\) (因为\(M_i\)是除\(m_i\)以外的模数的倍数)

∵ $M_i t_i≡1 ~ ( ~ mod ~ m_i ~ ) $

∴ $ a_i M_i t_i ≡ a_i ~ ( ~ mod ~ m_i ~ )$

过程:

其实就是把\(n\)个方程经过\(n-1\)次合并,最后成为一个方程求解就好了。

首先提出两个方程

\[ \left\{ \begin{matrix}x ≡ ~ a_1 ~ (~ mod ~ m_1 ~ )\\x ≡ ~ a_2 ~ (~ mod ~ m_2 ~ )\\\end{matrix} \right. \]

将其转化为

\[ \left\{ \begin{matrix}x ≡ k_1 m_1+a_1\\x ≡ k_2 m_2+a_2\\\end{matrix} \right. \]

易得

\[ k_1 m_1 + a_1=k_2 m_2 + a_2 \]

整理得

\[ k_1 m_1 - k_2 m_2= a_2 - a_1 \]

然后用扩展欧几里得求出\(k_1\)\(-k_2\),当且仅当 \(gcd(m_1 , m_2) ~ | ~ a_2 - a_1\) 时有解。

设$$d=gcd(m_1 , m_2)$$

\[x=(k_1+k*\frac{m_2}{d})m_1+a_1 \]

\[=m_1 k_1+a_1+k*lcm \]

设$$m_1 k_1= A,lcm=M$$

\[∴ ~ x = k M + A \]

因此,

\[ \left\{ \begin{matrix}x ≡ ~ a_1 ~ (~ mod ~ m_1 ~ )\\x ≡ ~ a_2 ~ (~ mod ~ m_2 ~ )\\\end{matrix} \right. \]

合并为

\[~ x = k M + A \]

在与下面的方程继续合并,最后合并为一个方程$$x = k M + A$$

此时,\(x\)的最小正整数解为 \(A ~ mod ~ M\) 的正余数。

代码:(【模板】中国剩余定理(CRT)/ 曹冲养猪)

$code$
#include<bits/stdc++.h>
using namespace std;
#define int  __int128
const int N=20;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
inline void write(int x){if(x<0)x*=-1,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');return;}
int m=1,a[N],b[N],n,k,s;
int exgcd(int a,int b,int &x,int &y){if(!b){x=1;y=0;return a;}int r=exgcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;return r;
}
signed main(){n=read();for(int i=1;i<=n;i++){a[i]=read();b[i]=read();m*=a[i];}for(int i=1;i<=n;i++){k=m/a[i];int x,y;exgcd(k,a[i],x,y);s=s+k*b[i]%m*x%m;}write((s%m+m)%m);return 0;
}

扩展中国剩余定理(exCRT)

...

扩展卢卡斯定理(exLucas)

...

http://www.hskmm.com/?act=detail&tid=28274

相关文章:

  • 没做完的题
  • 第十一天
  • JavaScriptDay1
  • 淘宝NPM镜像地址https://registry.npm.taobao.org不可用
  • 星星充电一面
  • 6 CF1034 div3 题解
  • 5 ABC413 题解
  • 4 CF 1032 div3 题解
  • 3 ABC411 C ~ E题解
  • 9 ABC408 D~F 题解
  • 8 ABC425 G 题解
  • 智能防御,安全赋能:AI-FOCUS 滤海AI DLP 化解外部 AI 风险
  • IDEA快捷键
  • VS code 中代码补全 自动补全函数括号
  • 优先队列
  • 学习ReAct并使用langgraph实现一个简单的ReAct AI Agent!!
  • abc 408 d~f
  • RMQ与LCA学习笔记
  • mamba-硬件感知算法
  • Java1
  • 完整教程:lua代码解析1
  • 二维数点
  • gitee和github如何修改仓库名并且保持与原远程仓库的连接?(手把手教学) - 实践
  • 2025.10.10总结 - A
  • [20251010]建立完善tpt的prr.sql脚本.txt
  • 第十一篇
  • testtest
  • 题解:AT_arc138_f [ARC138F] KD Tree
  • SP33 TRIP - Trip 个人题解
  • 经营不是老板一个人的事 - 智慧园区