ACM-学习记录-数论

本文最后更新于:2020年11月21日 晚上

GCD,LCM

定理

a、b两个数的最大公约数乘以它们最小公倍数等于a和b的乘积

axb=GCD(a,b)xLCM(a,b)

据此定理,求3与8的最小公倍数可以为:LCM(3,8)=3x8divGCD(3,8)=24

欧几里得算法

构造关系:GCD(a,b)=GCD(b, a mod b)

1
2
3
4
5
6
int gcd(int a,int b) 
{
if(b==0)
return a;
return gcd(b,a%b);
}

二进制最大公约数算法

  1. 递归终止条件:GCD(m,m)=m

  2. 递归关系式:

    m<n时:GCD(m,n)=GCD(n,m)

    m为偶数,n为偶数:Gcd(m,n)=2*Gcd(m/2,n/2)
    m为偶数,n为奇数:Gcd(m,n)=Gcd(m/2,n)
    m为奇数,n为偶数:Gcd(m,n)=Gcd(m,n/2)
    m为奇数,n为奇数:Gcd(m,n)=Gcd(n,m-n)

不定方程的整数解

方程ax+by=c有整数解的充要条件:gcd(a,b) | c

设d=gcd(a,b)

则若我们求得一组(x0,y0)满足ax0+by0=d

则可以得到原方程的一组解:((x0Xc)/d, (y0xc)/d)

扩展欧几里得算法

作用

已知a,b,求解一组x,y,使他们满足贝祖等式[^ax+by=gcd(a,b)=d](根据数论原理,解一定存在)。常用在求解模线性方程组中,也可以用来求解乘法逆元。

1
2
3
4
5
6
7
8
9
10
11
Int exGcd(int a,int b,int& x,int& y)
{
if(b==0)
{
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;
}

勾股数

勾股数有如下几个性质:

  1. X,Y,Z一定两两互质
  2. X,Y一定一奇一偶
  3. X+Z一定是一个完全平方数
  4. (Y+Z)/2也是一个完全平方数
  5. XxYxZ一定能被60整除

应用举例

​ 编程求n个(n≤100)正整数Ai(Ai≤30000,1≤i≤n)的最大公约数和最小公倍数。假设解一定在长整数范围内。

先求出两个数的最大公约数(最小公倍数),再和其他数求最大公约数(最小公倍数),只需调用函数n-1次。可以利用欧几里得算法快速实现:gcd(a1,a2,…,an)=gcd(gcd(a1,a2,…,an-1),an)

​ 阶乘问题

​ 整数n的阶乘n!是从1到n的所有整数的乘积。编程:输入一正整数n(n≤65000),给出n!的值从右至左有多少位连续的零?并输出n!的值从右至左第一个非零位的值。
​ 例如:n=5,则5!的值等于120,从右至左有1位连续的0;从右至左第一个非零的值为2。你的输出:
​ 1
​ 2
​ 当n=11时,程序应该输出:
​ 2
​ 8

​ 分析:

​ N!的值从右至左连续零的个数,实际上等于n!中所包含的5的因子的总数,这是因为:2x5=10.而n!中包含的2的因子的总数显然比5的因子总数大得多。

​ 在去除了所有从右至左连续的零以后,计算n!的最右非零位数值就可以用以下的公式:

1
(axb)%10=(a%10)x(b%10)%10

同余

定义

a%m=b%m,则称a,b mod m同余

概念

设a,b为两个整数,且它们的差a-b能被某个自然数m所整除,则就称a就模m来说同余于b,或者说a和b关于模m同余,

​ 记为:a=b (mod m)

它意味着:a-b=mxk(k为整数)

性质

对于整数a,b,c和自然数m,n则对模m同余满足:

  1. 自反性:a = a(mod m)

  2. 对成性:若a=b(mod m),则b = a(mod m)

  3. 传递性:若a=b(mod m),b=c(mod m),则a=c(mod m)

  4. 同加性:若a=b(mod m),则a+c=b+c(mod m)

  5. 同乘性:若a=b(mod m),则aXc=bXc

    ​ 一般情况,a=b(mod m),c=d(mod m),则:aXc=bXd(mod m)

  6. 同幂性:若a=b(mod m)则a^n=b^n(mod m)

  7. 若a mod p=x, a mod q=x,p、q互质,则a mod(pXq)=x

    但是同余不满足同除性,即:a/n != b/n(mod m)

素数

素数的几个定理

唯一分解定理

​ 若整数a>=2,那么a一定可以表示为若干个素数的乘积(唯一的形式),即a=p1xp2xp3x…ps(其中pj为素数,称为a的素因子,1<=j<=s)


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!