本文最后更新于 906 天前,其中的信息可能已经有所发展或是发生改变。
例题1 两个数的最大公约数
原题链接
描述
输入2个正整数a,b,求a与b的最大公约数。
输入
2个正整数a,b,中间用空格隔开。(1<=a,b <= 104)
输出
输出a与b的最大公约数。
样例输入
样例输出
代码 1
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| int main(){ |
| |
| int a, b; |
| |
| cin >> a >> b; |
| |
| int flag = 1; |
| |
| for(int i = 2; i <= min(a,b); i++){ |
| if(a % i == 0 && b % i == 0) flag = max(flag,i); |
| } |
| |
| cout << flag << "\n"; |
| |
| return 0; |
| |
| } |
代码 2
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| int gcd(int a, int b){ |
| return b ? gcd(b,a%b) : a; |
| } |
| |
| int main(){ |
| |
| int a, b; |
| |
| cin >> a >> b; |
| |
| cout << gcd(a,b) << "\n"; |
| |
| return 0; |
| |
| } |
数学题在算法竞赛中经常出现,在竞赛中经常把数学模型和其他算法结合起来,出综合性的题目。
分类:
- 整除性问题:整除、最大公约数、最大公倍数;欧几里得算法、扩展欧几里得算法。
- 公式计算:高精度计算、概率和数学期望
- 素数问题:素数判定、筛法、区间素数统计。
- 同余问题:模运算、同余方程、快速幂、中国剩余定理、逆元、整数分解、同余定理、不定方程。
- 积性函数:欧拉函数、伪随机数、莫比乌斯反演。
- 多项式与生成函数:快速傅里叶变换、普通生成函数、指数生成函数。
- 递推关系:Fibonacci数列、Stirling数、Catalan数。
- 群论:Polya定理。
- 线性规划:单纯形法。
- 线性代数:矩阵、高斯消元。
- 博弈论:公平组合游戏、非公平组合游戏。
- 排列组合:容斥原理、抽屉原理、康托展开、排列生成、组合生成
特点
- 涉及大量数学定理、数学模型和公式计算,综合程度高
- 需要将题目抽象出其数学模型,或根据条件推理出规律进行求解
概念
- 最大公约数指两个或多个整数共有约(因)数中最大的数
- 最小公倍数指两个或多个整数的公倍数里最小的数
- 欧几里得算法:又称辗转相除法,用于计算两个非负整数 a 和 b 的最大公约数
思想
-
辗转相除法求最大公约数
求100和18的最大公约数?
-
1.令a0=100,b0=18⌊b0a0⌋=5,a0−⌊b0a0⌋×b0=102.令a1=b0=18,b1=a0 mod b0=10⌊b1a1⌋=1,a1−⌊b1a1⌋×b1=83.令a2=b1=10,b2=a1 mod b1=8⌊b2a2⌋=1,a2−⌊b2a2⌋×b2=24.令a3=b2=8,b3=a2 mod b2=2⌊b3a3⌋=0,a3−⌊b3a3⌋×b3=4即最大公约数为b3=2
求 100 和18 两个正整数的最大公约数,用欧几里得算法,是这样进行的:
100 / 18 = 5 (余 10) 100%8=10
18 / 10= 1(余8) 18%10=8
10 / 8 = 1(余2) 10%8=2
8 / 2 = 4 (余0) 8%2=0
至此,最大公约数为2
以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 100 和 18 的最大公约数2。
-
求N和M的最小公倍数lcm(N,M),则先求N和M的最大公约数gcd(N,M),然后gcd(N,M)N×M则为最小公倍数。
| |
| int gcd(int a, int b){ |
| return b ? gcd(b, a % b) : a; |
| } |
| |
| |
| int lcm(int a,int b){ |
| return a / gcd(a,b) * b; |
| } |
原题链接
描述
输入两个正整数a、b,求a、b的最大公约数。要求采用递归函数实现。
输入
输入两个正整数a、b。
输出
输出a、b的最大公约数。
样例输出
样例输出
代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| int gcd(int a, int b){ |
| return b ? gcd(b,a % b) : a; |
| } |
| |
| int main(){ |
| |
| int a, b; |
| |
| cin >> a >> b; |
| |
| cout << gcd(a,b) << "\n"; |
| |
| return 0; |
| |
| } |
原题链接
题目描述
输入n个数,请计算它们的最小公倍数。如5、7、15的最小公倍数是105。
输入
首先输入一个正整数T,表示测试数据的组数,然后是T组的测试数据。
每组测试先输入一个整数n(2<=n<=20),再输入n个正整数(n属于[1,100000]),这里保证最终的结果在int型范围内。
输出
对于每组测试,输出n个整数的最小公倍数。
样例输入
样例输出
分析
代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| int gcd(int a,int b){ |
| return b ? gcd(b,a % b) : a; |
| } |
| |
| int lcm(int a,int b){ |
| return a / gcd(a,b) * b; |
| } |
| |
| void solve(){ |
| |
| int n; |
| |
| cin >> n; |
| |
| int t; |
| |
| cin >> t; |
| |
| for(int i = 2; i <= n ; i++){ |
| int x; |
| cin >> x; |
| |
| t = lcm(t,x); |
| |
| if(i == n) cout << t << '\n'; |
| |
| } |
| |
| } |
| |
| int main(){ |
| |
| int _; |
| |
| cin >> _; |
| |
| while(_--){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |
作用
- 求形如ax+by=gcd(a,b)的方程的解x,y
思想
-
欧几里得算法:gcd(a,b)=gcd(b,a%b),特别的gcd(a,0)=a
-
裴蜀定理:对于任意正整数a,b,一定存在非零的x,y,使得ax+by=gcd(a,b)
-
⎩⎨⎧b=0时:{gcd(a,b)=aax+by=gcd(a,b)⇒{x=1y=0b=0时:⎩⎨⎧①又②又③设 ax+by=gcd(a,b)=d∵由欧几里得算法可知:gcd(a,b)=gcd(b,a%b)=d∴由裴蜀定理得:bx′+(a%b)y′=d∵ax+by=d∴联立⎩⎨⎧ax+by=dbx′+(a%b)y′=da%b=a−⌊ba⌋b⇒{x=y′y=x′−⌊ba⌋y′设a′=b,b′=a%b∴gcd(b,a%b)=gcd(a′,b′)=d∵gcd(a′,b′)=gcd(b′,a′%b′)=d∴b′x′′+a′%b′y′′=d∵bx′+(a%b)y′=d∴联立⎩⎨⎧bx′+(a%b)y′=db′x′′+a′%b′y′′=da′%b′=a′−⌊b′a′⌋b′⇒{x′=y′′y′=x′′−⌊b′a′⌋y′′设a′′=b′,b′′=a′%b′……直到b=0时,联立解得{xi=1yi=0然后逐步返回每一次联立所得的结果{xi−1=yiyi−1=xi−⌊biai⌋yi最后返回得到x和y的值
注意
-
当方程符合ax+by=gcd(a,b)的形式时,才可以用扩展欧几里得算法求解(x0,y0)
-
推论:可以进一步求解任意方程ax+by=n,得到一个整数解
-
⎩⎨⎧(1) 判断方程ax+by=n是否有整数解,有解的条件为:gcd(a,b)可以整除n(2) 用扩展欧几里得算法求ax+by=gcd(a,b)得到一个解(x0,y0)(3) 在ax0+by0=gcd(a,b)两边同时乘gcd(a,b)n⇒gcd(a,b)ax0n+gcd(a,b)by0n=n(4) 对照ax+by=n可知该方程的一个解为(x′,y′),其中⎩⎨⎧x′=gcd(a,b)x0ny′=gcd(a,b)y0n
| void exgcd(int a, int b, int &x, int &y){ |
| |
| if(!b){ |
| x = 1,y = 0; |
| return ; |
| } |
| else{ |
| exgcd(b, a % b, x, y); |
| int t = x; |
| x = y; |
| y = t - a / b * y; |
| } |
| |
| } |
原题链接
描述
给定n对正整数 ai,bi,对于每对数,求出一组 xi,yi,使其满足 ai×xi+bi×yi=gcd(ai,bi)。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含两个整数 ai,bi。
输出格式
输出共 n 行,对于每组ai,bi,求出一组满足条件的 xi,yi,每组结果占一行。
本题答案不唯一,输出任意满足条件的 xi,yi 均可。
数据范围
1≤n≤105,
1≤ai,bi≤2×109
输入样例:
输出样例:
代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| void exgcd(int a,int b,int &x,int &y){ |
| |
| if(!b){x=1,y=0; |
| return ;} |
| else{ |
| |
| exgcd(b,a%b,x,y); |
| int t=x; |
| x=y; |
| y=t-a/b*y; |
| } |
| |
| } |
| |
| int main(){ |
| |
| int n; |
| |
| cin>>n; |
| |
| while(n--){ |
| |
| int a,b,x,y; |
| |
| cin>>a>>b; |
| |
| exgcd(a,b,x,y); |
| |
| cout<<x<<" "<<y<<endl; |
| |
| } |
| |
| return 0; |
| |
| } |
概念
- ax≡b(mod m),即max与mb的余数相同,且a,b,m为整数,求x的值
- 该方程即为一元线性同余方程
思想
-
对ax≡b(mod m)做等价变形:ax+my=b
-
又∵∴∴∴∵∴∴∵∴axax%max−⌊max⌋max−kb⌊max⌋,(⌊max⌋设(⌊max⌋ax−kbyax≡b(mod ≡b(mod m)=k(b%m),(k∈Z)=k(b−⌊mb⌋m)=(⌊max⌋−k⌊mb⌋)m⌊mb⌋,k∈Z−k⌊mb⌋)∈Z−k⌊mb⌋)=y,(y∈Z)=my⇒ax−my=b可以为负数m)↔ax+my=b
-
由扩展欧几里得算法的推论可知:当且仅当gcd(a,m)可以整除b时,ax+my=b存在整数解
-
由扩展欧几里得算法可知:⎩⎨⎧当gcd(a,m)=b时:{x=x0y=y0当gcd(a,m)为b的整数倍时:{x′=gcd(a,m)x0by′=gcd(a,m)y0b
例题 878. 线性同余方程
原题链接
描述
给定 n 组数据 ai,bi,mi,对于每组数求出一个 xi,使其满足 ai×xi≡bi(mod mi),如果无解则输出 impossible
。
输入格式
第一行包含整数 n。
接下来 n行,每行包含一组数据 ai,bi,mi。
输出格式
输出共 n 行,每组数据输出一个整数表示一个满足条件的 xi,如果无解则输出 impossible
。
每组数据结果占一行,结果可能不唯一,输出任意一个满足条件的结果均可。
输出答案必须在 int
范围之内。
数据范围
1≤n≤105,
1≤ai,bi,mi≤2×109
输出样例:
输出样例:
代码
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| typedef long long LL; |
| |
| LL gcd(LL a,LL b){ |
| return b ? gcd(b,a % b) : a; |
| } |
| |
| void exgcd(LL a,LL b,LL &x,LL &y){ |
| |
| if(!b){ |
| x=1,y=0; |
| return ; |
| } |
| else{ |
| exgcd(b,a%b,x,y); |
| LL t=x; |
| x=y; |
| y=t-a/b*y; |
| } |
| |
| } |
| |
| int main(){ |
| |
| int n; |
| |
| cin>>n; |
| |
| while(n--){ |
| |
| LL a,b,m,x,y; |
| |
| cin>>a>>b>>m; |
| |
| LL d=gcd(a,m); |
| |
| exgcd(a,m,x,y); |
| |
| if(b%d) cout<<"impossible"<<endl; |
| else cout<<b/d*x%m<<endl; |
| |
| } |
| |
| return 0; |
| |
| } |