自动搬运

查看原文

来自洛谷，原作者为

	Flandre_495 天魔山巅雪驹草，三途河畔彼岸花

搬运于2025-08-24 21:37:21，当前版本为作者最后更新于2019-09-11 10:16:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

真是个无人区啊~

提交通过数都这么少。。。

但是！_rqy竟然做了这道题！所以我打算尝试一下。。。

首先更正一下楼下的题解。

下面的题解好像有点问题。。。这题统计答案时是不能贪心的，需要用背包。但数据太弱，所以

比如质因数分解后是2 3 5 7，最优的肯定是3,5放一起，2,7放一起，但如果从前往后枚举的话，就只能更新$2*3*5$。

以上是对楼下题解的更正，所以对于楼下错误的写法，这篇就是唯一正确的了？

那我们回到题目：

思路看楼下的题解就行了~，楼下讲的还是很清楚的。

设输入的是a和b。

先把a和b两个数相除，将得到的数c分解。

我们要求一对x,y，使x,y互质，且$x*y=c$。

这样$x*a,y*a$就是我们的答案，满足最大公因数是a，最小公倍数是b（$b =x*y/a$）。

所以我们要将c的质因数分给x和y，但每个质因数只能属于x或y，如果x，y出现了相同的质因数，那么他们就不会互质。

所以我们现在的任务是将质因数分给x和y，并使x+y最小，我们已知$x*y=c$，所以x与y的差越小越好，初中知识。。

我们开一个背包，使x能越接近$\sqrt{c}$就越好。

那么最后输出x和y与a的乘积就行。

详见代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define QWQ cout<<"QwQ"<<endl;
#define ll long long 
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
const ll N=101010;
const ll qwq=202020;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll a,b,c;
ll x, y;
ll pre[N], cnt;
vector <int> ans;

int main() {
	while(cin>>a>>b) {
		cnt = 0; ans.clear();
		if(a==0||b==0) {
			printf("0 0\n");
			continue;
		}
		c = b / a;
		ll c1 = c;
		for(ll i=2;i<=c1;i++) {
			if(c1%i==0) pre[++cnt] = 1;
			while(c1%i==0) {
				pre[cnt] *= i;
				c1 /= i;
			}
		}
		ans.push_back(1);
		for(int i=1;i<=cnt;i++) {
			int len = ans.size();
			for(int j=0;j<len;j++) {
				if(ans[j]*pre[i] > sqrt(c)) continue;
				ans.push_back( ans[j]*pre[i] );
			}
		}
		sort(ans.begin(),ans.end());
		x = ans[ans.size()-1];
		y = c / x;
		cout<<x*a<<" "<<y*a<<endl;
	}
	return 0;
}

最后注意这个沙雕的细节：a，b均为0时x，y也是0。