一、最大公因数

1.定义

• 设$a_1,...,a_n$是$n(n\ge 2)$个整数。若整数$d$是它们中每一个数的因数，则$d$就叫做$a_1,...,a_n$的一个公因数。

• 设$a_1,...,a_n$不全为$0$。那么整数$a_1,...,a_n$的所有公因数中最大的一个公因数就叫做最大公因数。若整记作$(a_1,...,a_n)$。

• 当$(a_1,...,a_n)=1$时，称$a_1,...,a_n$互素或互质。

2.性质

• 设$a_1,...,a_n$是$n$个不全为零的整数，则：

  • $a_1,...,a_n$与$|a_1|,...,|a_n|$的公因数相同
  • $(a_1,...,a_n)=(|a_1|,...,|a_n|)$

• 设$b$是任一正整数，则$(0,b)=b$。

• $[a,b]=\frac{ab}{(a,b)}$

3.求解最大公因数

（1）暴力法

暴力枚举每一个数，并暴力的去寻找每一个数的因数，以此来更新当前的最大公因数。

ll gcd=a[1];
for(ll i=2;i<=n;i++)
{for(ll j=min(gcd,a[i]);j>=2;j--){if(a[i]%j==0 && gcd%j==0){gcd=j;break;}}
}

时间复杂度$O(n\cdot avg)$。

（2）辗转相除法

性质：设$a,b,c$是三个不全为$0$的整数，并假设$a>b$，$q$也是整数。如果$a=q\cdot b+c$，则$(a,b)=(b,c)$。

故而，要求$(a,b)$只需求$(b,c)$即可，如此反复即为辗转相除法，时间复杂度大大降低。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>using namespace std;
typedef long long ll;ll gcd(ll a,ll b)
{if(b==0)return a;return gcd(b,a%b);
}
int main()
{ll num[100],n;cin>>n;for(ll i=1;i<=n;i++)cin>>num[i];ll ans=0;for(ll i=1;i<=n;i++)ans=gcd(ans,num[i]);cout<<ans<<endl;return 0;
}

辗转相除法本身的时间复杂度为$O(logalo{g}^{2}b)$。

二、同余的基本介绍

1.定义

给定一个正整数$m$，两个整数$a,b$叫做模$m$同余，如果$a-b$被$m$整除，或$m|a-b$，就记作$a\equiv b(modm)$。否则，叫做模$m$不同余，记作$a\not\equiv b(modm)$。

2.基本性质

• 自反性：对任一整数$a$，有$a\equiv a(modm)$。
• 对称性：若$a\equiv b(modm)$，则$b\equiv a(modm)$.
• 传递性：若$a\equiv b(modm)$，$b\equiv c(modm)$，则$a\equiv c(modm)$。

若一个关系有上面三个关系，则称为等价关系。

三、同余的运算

1.加法与乘法

设$m$是一个正整数，设$a_1,a_2,b_1,b_2$是$4$个整数，如果：
$$a_1\equiv b_1(modm),a_2\equiv b_2(modm)$$
则可以满足以下运算规则：

• $a_1+a_2\equiv b_1+b_2(modm)$
• $a_1\cdot a_2\equiv b_1\cdot b_2(modm)$

2.运算性质

• 设$m$是一个正整数，设$d\cdot a\equiv d\cdot b(modm)$。如果$(d,m)=1$，则$a\equiv b(modm)$。

• 设$m$是一个正整数，设$a\equiv b(modm),d>0$，则$d\cdot a\equiv d\cdot b(modd\cdot m)$。

• 设$m$是一个正整数，设$a\equiv b(modm)$，如果整数$d|(a,b,m)$，则$\frac{a}{d}\equiv \frac{b}{d}(mod\frac{m}{d})$。

• 设$m_1,...,m_k$是$k$个正整数，设$a\equiv b(mod{m}_i),i=1,...,k$，则$a\equiv b(mod[m_1,...,m_k])$。

3.快速幂

ll quickpow(ll a,ll p,ll mod)
{if(a==0)return 0;while(p){if(p&1)ans=ans*a%mod;a=a*a%mod;p>>=1;}return ans;
}

四、作业

P1888 三角函数

P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

P1372 又是毕业季I

P1414 又是毕业季II