基础知识
最大公约数:
最大公约数就是两个数的最大公共因子
x = abc , y = bcdef(a ~ f均为质因子)
则gcd ( x , y ) = bc
计算方法:
1.质因数分解法,如上举例所示
2.欧几里得算法(辗转相除法)
算法原理:gcd(a,b) = gcd( b , a % b)
三目运算符(较快)
int gcd(int a , int b ){
return !b ? a : gcd(b, a % b);
}
位运算(超快)( a , b不能为0)
int gcd(int a , int b){
while(b ^= a ^= b ^= a %= b);
return a;
}
分析:
b^=a^=b^=a%=b可以写为 a%=b , b ^= a , a ^= b , b ^= a ;
后面三句相当于swap(a , b)
于是就变为a %= b , swap(a , b)
这就是最基本的辗转相除法
https://blog.csdn.net/Ljnoit/article/details/104604806
最小公倍数
最小公倍数是两个数的所有质因子的积
x = abc , y = bcdef(均为质因子)
则lcm(x , y ) = abcdef
(分式加减时都要将分母化为最小公倍数)
计算方法:
lcm( a , b ) = a * b / gcd( a , b )
常用性质
- gcd(a,b)∗lcm(a,b)=a *b
- 若gcd(a , b) = m, 则gcd( a/m , b/m ) = 1
- 同理,若lcm( a , b ) = k , 则 gcd( k/b , k/a ) = 1
例题
1.最大公约数与最小公倍数问题
(https://www.luogu.com.cn/problem/P1029)
解题思路:
gcd(P,Q) = x0, lcm(P,Q) = y0可推出x0 <= P , Q <= y0
确定了范围,然后双层遍历,看是否满足条件就好这样会超时,所以要将算法优化到O(N)
将Q用P表示就好,利用性质gcd(P, Q)∗lcm(P, Q)= P * Q
Q = x0 * y0 / P;
注意:
遍历从x0 ~ sqrt(x0*y0)是因为结果P * Q和 结果Q * P ,只用算一次,之后再乘2就好,但是如果x0 == y0,只用 加1次
代码:
#include<bits/stdc++.h>
using namespace std;
int gcd(int a , int b){
return !b ? a : gcd(b, a%b);
}
int main(){
int x0,y0;
cin >> x0 >> y0;
int t = x0 * y0;
int ans = 0;
for(int i = x0 ; i < (int)sqrt(t) ; i++){
if(t % i == 0 && gcd(t/i , i) == x0){
ans++;
}
}
if(t % (int)sqrt(t) == 0 && gcd(t / (int)sqrt(t),(int)sqrt(t)) == x0)
cout << ans*2 + 1 << endl;
else
cout << ans*2 << endl;
return 0;
}
2.P1072 Hankson的趣味题
https://www.luogu.com.cn/problem/P1072
比较好的题解:https://www.luogu.com.cn/blog/zzlzk/solution-p1072
题意:
输入四个数,a0,a1,b0,b1 求x使得条件:
1.x 和a0的最大公约数是a1;
2.x 和b0的最小公倍数是b1。
问x的个数
解题思路:
由题意能得到的信息
- x一定时最小公倍数 b1 的因子,一定是最大公约数 a1 的倍数,a1 <= x <= b1
我们要做的就是从1到sqrt(b1)遍历其因子,且该因子能 整除 a1,
同时它还要满足题中的两个条件,如果都满足 ans++
注意:相等因子只加一次
*** 这里有个问题,如果按照题中条件判断有可能爆int导致判断不准,所以我们要对条件进行处理
用到了性质
- 若gcd(a , b) = m , 则 gcd( a/m , b/m ) = 1
- 同理,若lcm( a , b ) = k , 则 gcd( k/b , k/a ) = 1
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(b > a)swap(a,b);
return !b ? a : gcd(b , a % b);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int a0,a1,b0,b1;
scanf("%d %d %d %d",&a0,&a1,&b0,&b1);
int ans = 0;
for(int i = 1 ; i * i <= b1; i++){
if(b1 % i != 0)continue;//不是因子,继续
if((i % a1 == 0) && gcd( i , a0 ) == a1 && gcd( b1/b0 , b1/i ) == 1){
ans++;
}
int j = b1 / i;
if(j == i)continue;//相等因子只判断一次
if((j % a1 == 0) && gcd( j , a0 ) == a1 && gcd( b1/b0 , b1/j ) == 1){
ans++;
}
}
printf("%dn",ans);
}
return 0;
}
如果还是不理解可以看上面大佬的博客
3.P4057 [Code+#1]晨跑
https://www.luogu.com.cn/problem/P4057
这个题比较简单,就是给出三个人每隔几天运动 的天数a,b,c,问三个人下次碰到是什么时候
就是三人的最小公倍数
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a , long long b){
if(!b)return a;
else return gcd(b,a%b);
}
int main(){
long long a,b,c;
scanf("%lld %lld %lld",&a,&b,&c);
long long ans = a / gcd(a,b) * b;
ans = ans / gcd(ans,c) * c;
printf("%lldn",ans);
return 0;
}
原文链接: https://www.cnblogs.com/w-w-t/p/13173019.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/199302
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!