最小公倍数 ((LCM))

最大公约数

公约数：几个整数共有的约数。（\( \pm 1是任何整数的公约数\)）

最大公约数：显而易见，所有公约数中最大的那个。

欧几里得算法

为了求最大公约数（常记为GCD），我们常用欧几里得算法。以两个数的最大公约数为例。设正整数a,b。不妨假设(a>b)。

证明

当 (b\mid a)时，很明显，(gcd(a,b)=b)。

当 (b\nmid a)时，设(a=k\times b+r,d=gcd(a,b))。那么 (r=a\ mod\ b,\ d\mid a且d\mid b)，等式同除(d)，得到 (\frac{a}{d}=k\times \frac{b}{d}+\frac{r}{d})，等式左侧为整数，则 (\frac{r}{d}) 也为整数。

Code

由此我们得到一个递归的写法

int gcd(int a,int b)

{


if(b==0)return a;<br/>
else return gcd(b,a%b);<br/>


}

令n为a,b之中的较大数，时间复杂度 (O(log\ n))。

更相减损术

由于大整数取模速度很慢，我们用加减法代替取模运算可以证明 \( \forall d \mid a,d \mid b,有d \mid a-b \)，因此

怎么求多个数的最大公约数?我们可以每次求其中两个整数的gcd，并将其放回原数列，继续求解，不会对结果有影响。

最小公倍数 ((LCM))

利用最大公约数求LCM

已知整数(a,b)，进行质因数分解

(a=p_{a1}^{k{a1}} \times p{a2}^{k{a2}} \times \ldots \times p{an}^{k{an}} ,b=p{b1}^{k{b1}} \times p{b2}^{k{b2}} \times \ldots \times p{bm}^{k{b_m}})

易知 \( gcd(a,b)=p_1^{min(k_{a_1},k_{b_1})} \times p_2^{min(k_{a_2},k_{b_2})} \times \ldots \times p_n^{min(k_{a_n},k_{b_n})} \) ， \( lcm(a,b)=p_1^{max(k_{a_1},k_{b_1})} \times p_2^{max(k_{a_2},k_{b_2})} \times \ldots \times p_n^{max(k_{a_n},k_{b_n})} \)

\(\because min(k_{a_i},k_{b_i}) \times max(k_{a_i},k_{b_i})=k_{a_i} \times k_{b_i} \)

\(\therefore gcd(a,b) \times lcm(a,b)=a \times b \)

用于求解关于 (x,y) 形如 \(ax+by=gcd(a,b) \)的方程的一组可行的整数解。

证明

当 \( gcd(a,b)=a \)时，显然有一组解 \( x=1,y=0 \)

对于一般情况，设 \( ax_1+by_1=gcd(a,b) \)

\( bx_2+(a \mod b)y=gcd(b,a\mod b) \)

由欧几里得可知，\( gcd(a,b)=gcd(b,a\mod b) \)

\( ax_1+by_1=bx_2+(a\mod b)y_2 \)

又因为 \( a\mod b=a-b\times \left \lfloor \frac{a}{b} \right \rfloor \) ，整理可得

由于我们只要得到一组解即可，令 \( x_1=y_2,\ y_1=x_2-\left \lfloor \frac{a}{b} \right \rfloor y_2 \)

Code

int exgcd(int a,int b,int &x,int &y)

{


if(!b){<br/>
    x=1;<br/>
    y=0;<br/>
    return a;<br/>
}<br/>
int d=exgcd(b,a%b,x,y);<br/>
int t=x;<br/>
x=y;<br/>
y=t-a/b*y;<br/>
return d;<br/>


}

例题 倒酒

普及OJ

提高OJ

思路

a mL的酒杯最后剩下的酒为b mL酒杯向 a中倒入的总酒量减a倒回酒桶的酒量，设a酒杯倒出x次，b酒杯倒入a酒杯y次，最后剩余酒的最小值为c。

得到方程 \( by-ax=c \)

那么何时c取最小值？其实就是 \( gcd(a,b) \)

证明

反证法，设整数 \( r<gcd(a,b)且 by-ax=r \)，令 \( d=gcd(a,b) \)

\( \because d=gcd(a,b) \ \) \( \therefore d \mid a 且 d \mid b \)

\( \because r<d \ \) \( \therefore d \nmid r \)

\( \because 等式左侧必为整数，等式右侧必为分数 \)

\( \therefore 假设不成立 \)

\( by-ax 的最小值为 gcd(a,b) \)

证毕

利用 (exgcd) 求出一组可行的解 (x_1,y_1) ，注意我们求解的方程是 \( ax+by=gcd(a,b) \) ， (x)取负数，方程就转换为 \( -ax+by=gcd(a,b) \) ，题干的要求是使 (x) 最小，同时保证 (x,y) 均为正整数，应该怎么处理？

令 \( a_1= \frac{a}{gcd(a,b)}, b_1= \frac{b}{gcd(a,b)} \)

则 \( a_1x_1+b_1y_1=1 \)

\( a_1 x_2+ a_1 \Delta x +b_1y_1=1 \)

\( a_1x_2+b_1(y_1+ \frac{a_1 \Delta x }{b_1} )=1 \)

\( \because y_2=y_1+ \frac{a_1 \Delta x}{b_1} 为正整数 \)

\( \therefore b_1 \mid a_1 \Delta x \)

\( \because gcd(a_1,b_1)=1 \)

\( \therefore b_1 \mid \Delta x \)

\( x_2=x_1- \Delta x \) 且 (x_2) 取最小正整数， \(x_2=x_1 \mod b_1 \)，因为 (x_1) 可能为负数 ，\( x_2=(x_1 \mod b_1+b_1 ) \mod b_1 \)

Code

#include<bits/stdc++.h>

using namespace std;

#define int long long

int a,b,c;

int x,y;

int exgcd(int a,int b,int &x,int &y)

{


if(!b){<br/>
    x=1;<br/>
    y=0;<br/>
    return a;<br/>
}<br/>
int d=exgcd(b,a%b,x,y);<br/>
int t=x;<br/>
x=y;<br/>
y=t-a/b*y;<br/>
return d;<br/>


}
signed main()

{


scanf(&#34;%lld%lld&#34;,&amp;a,&amp;b);<br/>
c=exgcd(a,b,x,y);<br/>
cout&lt;&lt;c&lt;&lt;endl;<br/>
x=-x;<br/>
b/=c;<br/>
a/=c;<br/>
c=1;<br/>
x=(x%b+b)%b;<br/>
y=(c+a*x)/b;<br/>
cout&lt;&lt;x&lt;&lt;&#39; &#39;&lt;&lt;y&lt;&lt;endl;<br/>


}

定义

关于 (a,p)的同余方程 \( ax \equiv 1 (\mod p ) \)， (x)称为 (a)在模 (p) 意义下的乘法逆元，其中 (a,p)互素 ， 记作 \( x=a^{-1} \)

性质

我们经常遇到这种场景，已知整数 \( a,b(很大，需要取模) \)，求 (a/b)。

由于a，b不能直接存下，只能进行取模，令 \( x=a\mod q,y=b\mod q \) ，这样问题就来了，取模之后在做除法不能保证结果正确。这时，乘法逆元启动。

\( x \times x^{-1} \equiv 1(\mod p) \)

由同余的相关性质可知， \( a\times x\times x^{-1} \equiv a(\mod p) \)

又 \( ax\div x\equiv a (\mod p) \)

由此，得出结论，在同余方程中，除以整数 (x)，相当于乘 (x)的逆元。

同时也可以证明 (a,p)不互素时，(a)没有逆元。

求逆元

单点求逆元

我们当然可以用扩展欧几里得解同余方程求逆元，这里不再解释。

也可以用快速幂和费马小定理求逆元，但蒟蒻不会，详见OI Wiki。

线性求逆元

求出 (1,2,\dots ,n) 中每个数在模 (p) 意义下的逆元，保证互素。

当 \( n\ge 1e7 \) 时 ，(O(n logn)) 求逆元就不现实了，考虑线性求逆元。

显然， \( 1^{-1}=1 \)

对于 (i\ne 1) 的情况， (p=ki+j)， \(k=\left \lfloor \frac{p}{i} \right \rfloor ,j=p \mod i \) 。

同乘 \(i^{-1}\times j^{-1} \)

保证 \(i^{-1}> 0 \)， \( i^{-1}=(p-\left \lfloor \frac{p}{i}\right \rfloor)\times (p\mod i)^{-1}\mod p \)

Code

#include<bits/stdc++.h>

using namespace std;

const int N=5e6;

#define int long long

int n,p;

int inv[N];

signed main()

{


cin&gt;&gt;n&gt;&gt;p;<br/>
inv[1]=1;<br/>
puts(&#34;1&#34;);<br/>
for(int i=2;i&lt;=n;i++){<br/>
    int k=p/i;<br/>
    int j=p%i;<br/>
    inv[i]=(long long)(p*k-inv[j]*k)%p;<br/>
    printf(&#34;%lld\n&#34;,inv[i]);<br/>
}<br/>


}