2 个问答
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5+10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int c, d;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>c>>d; // c 是最大公约数,d是最小公倍数
LL tmp = c * d;
unordered_map<int,int> ha;
for(int i=2;i<=tmp/i;i++){
if(tmp%i==0){
int s = 0;
while(tmp%i==0) s++,tmp/=i;
ha[i] = s;
}
}
if(tmp>1) ha[tmp] ++;
tmp = c;
for(int i=2;i<=tmp/i;i++){
if(c%i==0){
int s = 0;
while(tmp%i==0) s++,tmp/=i;
ha[i] -= 2 * s;
}
}
if(tmp>1) ha[tmp] -= 2;
LL a = c, b = c;
for(auto [x, y]:ha)
if(y>0){
for(int i=0;i<y;i++) b *= x;
}
cout<<a+b<<endl;
return 0;
}
有gcd和lcm可以知道ab的乘积,然后根据ab的乘积可以知道这个乘积中包含了两个gcd,用这个乘积除以两次gcd,应该可以得到一组互质的数,这组数分别*gcd就是a跟b。
但是我在考虑a和b是不是总是唯一的呢?根据我的思路的话,我们总是能根据乘积得到一个数,将这个数分解为两个互质的数,从而得到a和b…但是题目又限制了gcd的数值,所以a和b总是唯一的??