【CodeForces-1029F】Multicolored Markers

【CodeForces-1029F】Multicolored Markers

Solution:

内部各自至少也要有一个是矩形,我们首先将可能的矩形存下来,之后枚举大矩形的时候判断一下它是否可能嵌套小矩形来决定当前方案是否可行就可以。

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;

inline LL mini(LL a, LL b) {return a < b ? a : b;}

vector<LL> boxa, boxb;

int main(void) {
    LL a, b;
    scanf("%lld%lld", &a, &b);
    LL area = a + b;
    LL lim = sqrt(a);
    for (int i = 1; i <= lim; i++) {
        if (a % i == 0) boxa.push_back(i);
    }
    lim = sqrt(b);
    for (int i = 1; i <= lim; i++) {
        if (b % i == 0) boxb.push_back(i);
    }
    lim = sqrt(area);
    // cout << lim << endl;
    LL ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= lim; i++) {
        if (area % i) continue;
        LL tmp = area / i;
        for (int j = 0; j < boxa.size(); j++) {
            if (boxa[j] <= i && a / boxa[j] <= tmp) {
                ans = mini((i + tmp) * 2, ans);
                break;
            }
        }
        for (int j = 0; j < boxb.size(); j++) {
            if (boxb[j] <= i && b / boxb[j] <= tmp) {
                ans = mini((i + tmp) * 2, ans);
                break;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}