整除和GCD

Nannan Lv5
  2023-11-05 17:41 2023-11-05 17:41 Created   2024-09-30 19:26:35 2024-09-30 19:26:35 Updated      

Divisor and Gcd

1、算术基本定理：n的质因数分解唯一

一些常见结论：
1.素数无限
2.(Π(n)表示<=n素数的个数)
————即n以下素数个数大约是 级别的
3.级别的 (Pn表示素数)
4.
5.

2.整除的常见性质:

a|b ：b能被a整除
1.若，，则。
证明：
$b = q1a,c = q2a b±c = q1a±q2a = (q1±q2)*a; ∴a|(b±c)a|c,b|c,(a,b) = 1(互质) ==> ab|ca|bc,(a,b) = 1 ==> a|cp|ab ==> p|a或p|b$

3.公约数和公倍数







竞赛中遇到能被xx整除的数的特征：

  1. 能被2整除的数：个位上为2的倍数
  2. 能被4整除的数：个位和十位所组成的两位数能被4整除
  3. 能被8整除的数：百位、个位、十位所组成的三位数能被8整除（注意顺序）
  4. 能被5整除的数：个位上为5的倍数
  5. 能被25整除的数：十位和个位所组成的两位数能被25整除
  6. 能被125整除的数：百位、十位、个位所组成的数能被125整除
  7. 能被3整除的数：各个数位上的数字和能被3整除
  8. 能被9整除的数：各个数位上的数字和能被9整除
  9. 能被11整除的数：奇数位（从左往右数）上的数字和与偶数位上的数字和的差的绝对值能被11整除
  10. 能被7整除的数：把个位数字截去，从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除，如果不好判断就递归处理
  11. 能被13整除的数：把个位数字截去，从余下的数中，加上个位数的4倍，如果和是13的倍数，则原数能被13整除
  12. 能被17整除的数：把个位数字截去，从余下的数中，加上个位数的5倍，如果和是17的倍数，则原数能被17整除，或把后三位截去，剩下的数与3倍后三位差的绝对值如果能被17整除，则原数能被17整除
  13. 能被19整除的数：把个位数字截去，从余下的数中，加上个位数的2倍，如果和是19的倍数，则原数能被19整除，或把后三位截去，剩下的数与7倍后三位的差的绝对值如果能被19整除，则原数能被19整除

4.求公约数

1.欧几里得算法

d = a[1];
for(i = 2;i<=n;i++)
d = gcd(d,a[i]);
时间复杂度O(n+log(max ai))

2.另一种公约数的算法

·如果a,b都是奇数,那么
·如果a是偶数,b是奇数,那么
·如果a,b都是偶数,那么

5.有关公约数和公倍数的题目

1. GCD and LCM - HDU 4497

题意：给你两个正整数和,你可以说出有多少组解满足并且

注意和这样是两个不同的解。

思路:从的性质考虑：

  1. 若，则

显然，若是无解的，那下面我们来看有解的情况：

转化为

转化为

那么现在问题转化为：满足互质的，且他们的

因为要满足互质的的条件，那么以{}为例，至少有一个是。

合法的情况是：

1){} 排列方式3种

2){} 排列方式3种

3){～} 排列方式种

综上，对于每一位有$3+3+(e_1-1)6 = 6e_1$

那么接下来问题转化为对进行质因数分解，再求种类数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll G,L;
		cin>>G>>L;
		if(L%G)
		{
			cout<<0<<endl;
			continue;
		}
		ll n = L/G;
		ll ans = 1;
		for(int i = 2;i<=n/i;i++)
		{
			if(n%i==0)
			{
				ll cnt = 0;
				while(n%i==0)
					n/=i,cnt++;
				ans*= 6ll*cnt;
			}
		}
		if(n>1)
			ans*=6ll;
		cout<<ans<<endl;
	}
	return 0;
}

2.【数论+完全背包】Least common multiple - HDU 3092

题意：如果给你一个数，我们把分成一些数字，问我们这些数字组最大的是多少，对结果取模？

思路：首先可以明确，分成的这几个数一定是互质的。为什么呢？假设有两个数不互质，那么他们的里面势必会少乘一个他们俩的，这样肯定不如都是互质的优。那么接下来，因为都是素数，那么我们可以先把素数预处理出来，然后用这些数填满，求填满时最大的。

很神奇的事情发生了，我们发现，是不是像我们有一个容量为的背包，有个物品，每个物品的体积是，可以取无限次。

对滴，是完全背包，那么接下来就可以开始写啦。

但是！这个时候我们又遇到一个问题，结果是要取模的，但是对于取模后的数我们是没有办法比大小的，中间步骤不取模又会炸，怎么办嘞？我们考虑用来帮忙。

若$ab<cd则有log^a+log^b < log^c+log^d$

因为在库函数里面是默认以为底的，单调递增，那么我们的相对顺序没有变，而缩小了数字本身的大小，达到不会炸又可以比较大小的效果。

那么通过以上，问题解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int N =2e4+10;
bool is_pri[N];
int pri[N];
int cnt;

void init(int n)
{
	memset(is_pri, true, sizeof(is_pri));
	is_pri[1] = false;
	cnt = 0;
	for (int i = 2; i <= n-1; i++)
	{
		if (is_pri[i])
			pri[++cnt] = i;
		for (int j = 1; j <= cnt && i * pri[j] <= n-1; j++)
		{
			is_pri[i * pri[j]] = false;
			if (i % pri[j] == 0)break;            
		}
	}
}

ll n,mod;
double dp[N];
ll ans[N];
int main()
{
	init(N);
	while(cin>>n>>mod)
	{
		for(int i = 0;i<=n;i++)
			dp[i] = 0,ans[i] = 1;
		for(ll i = 1;i<=cnt&&pri[i]<=n;i++)//枚举物品
		{
			for(ll j = n;j>=pri[i];j--)//枚举体积
			{
				for(ll k = 1,now = pri[i];now<=j;now*=pri[i],k++)//枚举拿多少个(素数幂次)
				{
					//取模了无法比大小,用log
					if(now<=j&&dp[j-now]+log(now*1.0)>dp[j])
					{
						dp[j] = dp[j-now]+log(now*1.0);
						ans[j] = ans[j-now]*now%mod;
						//cout<<dp[j]<<endl;
					}
				}
			}
		}
		cout<<ans[n]%mod<<endl;
	}
	return 0;
}

6. 裴蜀定理(Bézout’s lemma)

定理内容：

是一个关于最大公约数的定理
其内容是：设是不全为零的整数，则存在整数 , 使得 存在整数解。

推论：整数互素当且仅当存在与使得

证明：对任意，，一定是的整数倍。最小的是

P4549 【模板】裴蜀定理

思路：首先看两对数的情况,改写成裴蜀定理写法就是。根据定理知的最小非负值就是，这样对于就合并成一个数,然后继续合并后面的。

由于会返回负数，那只需要最后一步加个绝对值就ok啦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin>>n;
	int x;
	cin>>x;
	for(int i = 2;i<=n;i++)
	{
		int y;
		cin>>y;
		x = __gcd(x,y);
	}
	cout<<abs(x)<<endl;
	return 0;
}

Pagodas - HDU 5512

思路：我们如果能得知最后能修的塔的数量，如果是奇数就先手赢，反之后手。

我们能修的塔：即，根据裴蜀定理知是的整数倍。

那么数量就是

7.线性丢番图方程

方程称为二元线性丢番图方程，其中是已知整数，是变量。

其实就是二维平面的一条直线，如果这条直线上有整数点那就有整数解,否则无。

如果存在一个解，那就有无数个解。

1.定理

因为,设是整数，且,如果不能被整除，那么方程无解，否则有无数解。

如果其中一个特解为，那么通解为：,其中为任意整数。

eg1.线段上格点数

题意：二维平面上，给定两个格点,问线段上除了外还有几个格点？设

题解：

线段

对照，那么

令特解为(这里用也一样),代入限制条件

那么：

当满足条件，那么有个格点。

eg1.[P1516青蛙的约会](P1516 青蛙的约会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) )

题意：

设青蛙 A 的出发点坐标是 ，青蛙 的出发点坐标是 。青蛙 一次能跳 米，青蛙 一次能跳 米，两只青蛙跳一次所花费的时间相同。纬度线总长 米。现在要你求出它们跳了几次以后才会碰面。

题解：

思路一：青蛙相遇时，初始位置的坐标差是与跳的距离的关系为

设

那么转化为我们常见的形式：,其中是我们要求的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#incldue<bits/stdc++.h>
using namespace std;

int main()
{
    ll n,m,x,y,L;
    cin>>n>>m>>x>>y>>L;
    ll a = n-m,b = L,c = x-y;
    if(a<0)a = -a,c = -c;//细节，exgcd的参数要是正的，我们处理一下负数。
    ll d = exgcd(a,b,x,y);
    if(c%d != 0)cout<<"impossible\n";
    else cout<<(x*(c/d)%(L/d)+(L/d))%(L%d)<<endl;
    
    return 0;
}

思路二：同余

设

则有注意这里a可能为负数,只对非负整数有意义，所以处理一下：若

那么,接下来我们求

由可解出就是

设,那么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p1,p2,m,n,l,a,b,x,y;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x = 1,y = 0;
		return a;
	}
	ll d = exgcd(b,a%b,y,x);
	y -= (a/b)*x;
	return d;
}

int main()
{
	cin>>p1>>p2>>m>>n>>l;
	/*
		(m-n)x ≡ (p2-p1)(mod l)
		(m-n)x + kl = (p2-p1)
		a = m-n,b = l,c = p2-p1;
		ax + by = c;
	*/
	ll a = n-m,b = l,c = p1-p2;
	if(a<0)a = -a,c = -c;
	ll d = exgcd(a,b,x,y);
	//ax0+by0 = d
	//ax0+by0能被d整除，那c也要能整除
	if(c%d)cout<<"Impossible\n";
	else{
		//ax+by = c
		//ax0*(c/d)+by0*(c/d) = c
		//x0*(c/d)是一个解
		cout<<(c/d*x%(b/d)+(b/d))%(b/d)<<endl;
	}
	return 0;
}

2.关于线性丢番图方程 ax+by=n 的解的个数

令是互素的正整数，是正整数。当和均非负时，线性丢番图方程的解是非负 的。

结论1：时，存在非负解。

证明：若是方程的一对特解(不一定为非负解)，则可以取到方程的所以解(其中为整数)

对于，存在解，此时有：

所以,所以此时存在非负解。

结论2：如果那么没有非负解。

证明：

若没有非负解，即

即，又因为互素

所以

令其中

把，代入

得，矛盾

所以此时没有非负解。

反过来：

不妨假设

设结果为，则

可得

当然时，显然可以用表示出来，不符合题意。

当时，满足条件的有最大值,显然时候，有的最大值

一种感性的解法：

引用自：(https://blog.csdn.net/dglyr/article/details/108135366 )

![image-20230713195242402](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230713195242402.png)

结论3：恰好有个非负整数使得方程有非负解。

8. 扩展欧几里得(exgcd)

扩展欧几里得算法实际上就是对于，一定有一组整数解x，y使其成立。

即扩展欧几里得是求的一组特解的方法。

如果要求的解，那么可以先利用求的一组特解，然后再两边同乘,

那么得到的一组解，其中

通解为：

具体做法：


由归纳假设存在使得
即

于是就得到了的解




商 余数

系数由

①
②

③

④



⑤

设可以找到一组解
那 ——————————————————再返回去找解

知道了特解之后，我们可以通过他求出方程的所有解

exgcd代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//输出ax−by=gcd(a,b)的最小非负整数解(x,y)
#include<bits/stdc++.h>
using namespace std;
//为了在计算最大公约数gcd(a,b)的同时,找到x,y,使得ax + by = d
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x = 1;
		y = 0;
		return a;
	}
	/*
	int xx,yy;
	int d = exgcd(b,a%b,xx,yy);
	x = yy,yy = xx-(a/b)*yy;
	*/

	/*
	int d = exgcd(b,a%b,x,y);
	int k = y;
	y = x-(a/b)*y;
	x = k;
	*/

	int d = exgcd(b,a%b,y,x);
	y -= (a/b)*x;
	return d;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int a,b,x,y;
		cin>>a>>b;
		int d = exgcd(a,b,x,y);
		// cout<<"gcd = "<<d<<endl;
		// cout<<"x = "<<x<<" y = "<<y<<endl;
		//对于ax+by = d特解是x ,y
		//通解就是x1 = x + b/(a,b)*t,y1 = y - a/(a,b)*t 

		//我们求的是ax + by = d;
		//要求ax-by = d
		//ax - b(-y) = d
		y = -y;
		//求最小正整数解，我们用exgcd求出的是最小整数解，有可能是负数的
		while(x<0||y<0)x+=b/d,y+=a/d;
		while(x>=b/d&&y>=a/d)x-=b/d,y-=a/d;
		cout<<x<<" "<<y<<endl;
	}
	return 0;
}

最小非负整数解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
输出ax+by=d的非负整数解a,b
两边同除gcd(a,b),得到a'x+b'y = d'
同样的两边可以同除d',当然如果不能整除那就无解
除完以后我们知道(a',b') = 1
我们求出一组解x0,y0
x1 = x0*d',y1 = y0*d'
x1>=0&&y1>=0且最小
通解：x1+b't   y1-a't
0<x1+b't<b'
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x = 1,y = 0;
		return a;
	}
	int d = exgcd(b,a%b,y,x);
	y -= (a/b)*x;
	return d;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int a,b,x,y;
		ll m;
		cin>>a>>b>>m;
		int d = exgcd(a,b,x,y);
		if(m%d!=0)
		{
			cout<<-1<<endl;
			continue;
		}
		//ax+by=m
		//都除掉d以后保证a,b互质
		a/=d;
		b/=d;
		m/=d;
		__int128 xx = (__int128)x*m;
		xx%=b;
		if(xx<0)xx+=b;
		__int128 yy = (m-a*xx)/b;
		if(yy<0)
			cout<<-1<<endl;
		else cout<<(ll)xx<<" "<<(ll)yy<<endl;
		
	}
	return 0;
}
  • Title: 整除和GCD
  • Author: Nannan
  • Created at : 2023-11-05 17:41:00
  • Updated at : 2024-09-30 19:26:35
  • Link: https://redefine.ohevan.com/2023/11/05/一、Divisor and GCD/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
整除和GCD
    1. Divisor and Gcd
      1. 1、算术基本定理：n的质因数分解唯一
      2. 2.整除的常见性质:
      3. 3.公约数和公倍数
        1. 竞赛中遇到能被xx整除的数的特征：
      4. 4.求公约数
        1. 1.欧几里得算法
        2. 2.另一种公约数的算法
      5. 5.有关公约数和公倍数的题目
        1. 1. GCD and LCM - HDU 4497
        2. 2.【数论+完全背包】Least common multiple - HDU 3092
      6. 6. 裴蜀定理(Bézout’s lemma)
        1. P4549 【模板】裴蜀定理
        2. Pagodas - HDU 5512
      7. 7.线性丢番图方程
        1. 1.定理
        2. eg1.线段上格点数
        3. eg1.[P1516青蛙的约会](P1516 青蛙的约会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) )
        4. 2.关于线性丢番图方程 ax+by=n 的解的个数
      8. 8. 扩展欧几里得(exgcd)
        1. exgcd代码演示