最大公约数（阿基里的算法）
最大公约数(lcm)
https://ac.nowcoder.com/acm/problem/16710
题目地址：https://ac.nowcoder.com/acm/problem/16710
没什么好说的，就是 gcd（nm) * lcm(n,m)=nm
但是由于n和m都比较大这里有一个讲究就是 结果要写成
n/ gcd *m
而不能写成 nm/gcd
因为乘法运算可能会导致数据越界而失精
代码如下：
#include<iostream>
#include<algorithm>
#include<set>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
#define close_stdin ios::sync_with_stdio(false)
#define P pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 0;
//欧几里得算法
ull gcd(ull a, ull b) {
return b ? gcd(b, a % b) : a; //不需要保证a>b
}
int main()
{
ull n, m;
cin >> n >> m;
cout << (n / gcd(n, m))*m;
}谢谢浏览
。
投递美团等公司9个岗位
查看1道真题和解析