一、Z上的带余除法

1.基本

满足a=b \cdot t,且a,b, t \in Z

b为a的因子或因数,a本身叫做b的倍数

a被b整除:b | a

a不能被b整除:b\not{|}a

注意:整除关系不是Z的一个等价关系(对称性不成立)。

2.性质

a,b,c \in Z
(1) a|a
(2) a|b,b|a \Leftrightarrow a= \pm b
(3) a|b,b|c \Rightarrow a|c
(4) a|b,a|c \Rightarrow a|(bu+cv),\forall u,v \in Z

3.定理

a,b \in Z,其中b \neq 0,则存在q,r \in Z,使得a=bq+r,0 \leqslant r<|b|,成立,而且q和r是惟一决定的,称q为a被b除的商数,称r为a被b除的余数。

4.代码实现

#include <iostream>
using namespace std; 
int main()
{
    int a,b,q,r;
    cin>>a>>b;
    if(b==0)//b等于0时等式无意义,程序结束
         return 0;
    q=a/b,r=a-b*q;
    cout<<a<<'='<<b<<'*'<<q<<(r<0?'-':'+')<<r<<endl; 
    return 0;
} 

二、最大公因子(数)

1.定义

设a,b是不全为0的整数

(1) 如果非0整数q同时是a与b的因子,即q|a,q|b,则称q是a与b的一个公因子(数)

(2) 如果a与b的公因子d满足,e|d,e为a与b的公因子,则称d是a与b的一个最大公因子(数)

对于有限多整数a_{1},a_{2},a_{3},…,a_{s} \in Z (s \geq 2),d \in Z,如果d有以下性质

(1) d|a_{i},i=1,2,3,…,s

(2) 若b|a_{i},i=1,2,3,…,s,则b|d

则称其为a_{1},a_{2},a_{3},…,a_{s}的一个最大公因子。a_{1},a_{2},a_{3},…,a_{s}全不为0时,用符号(a_{1},a_{2},a_{3},…,a_{s})表示正的最大公因子

2.注意

(1) gcd(0,0)=0,或(0,0)=0

(2) 如果d,e都为a与b的最大公因子,那么d= \pm e

3.定理

\forall不全为0的整数a,b都有最大公因子,可以表示为ua+vb,其中u,v \in Z

4.性质

a,b,q,r \in Z,有a=qb+r,则gcd(a,b)=(b,r)(辗转相除法的原理)

5.代码实现

(1) 两数

//库函数实现
#include <iostream>
#include <algorithm>
using namespace std; 
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<__gcd(a,b);
    return 0;
}
//辗转相除法
#include <iostream>
using namespace std;
int gcd(int a,int b)//递归法 
{
    return b==0?a:gcd(b,a%b);
}
/*int gcd(int a,int b)//非递归 
{
    int r;
    while(b)
    {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}*/
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
    return 0;
} 

(2) 多数

#include <iostream>
#include <cstring>
using namespace std;
const int N=1e7+1;
int a[N],n,maxa;
bool isprime[N];
void work(int p)//埃氏筛法
{
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;
    for (int i = 2; i<=p; ++i)
    {
        if (isprime[i]==0) 
            continue;
        for (int j = i + i; j<=p; j += i)
        {
            isprime[j] = false;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        if(a[i]<=0)
        {
            cout<<"e!pls try again!\n";
            cin>>a[i];
        }
        maxa<a[i]?maxa=a[i]:0;
    }
    work(maxa);
    for(int i=maxa;i>=0;--i)
    {
        bool ans=1;
        if(isprime[i]==0)
            continue;
        else for(int j=1;j<=n;++j)
        {
            if(a[j]%i!=0)
            {
                ans=0;
                break;
            }
        }
        if(ans==1)
        {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}