题解 P2406 【最小和】

· · 题解

真是个无人区啊~

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

但是！_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。