Codeforces 490D Chocolate：質因子分解最小操作數

Codeforces 490D Chocolate：質因子分解最小操作數

兩個矩形 (a₁,b₁), (a₂,b₂)。操作：1) 某邊 ÷2（需能被 2 整除）；2) 某邊 ×2/3（需能被 3 整除）。求最少操作使面積相等，並輸出最終邊長。

核心洞察：質因子視角

操作本質：

• 操作 1：移除一個質因子 2
• 操作 2：將一個質因子 3 轉化為質因子 2
• 其他質因子（5,7,11...）不可改變

算法流程

1. 分解四條邊的質因子，統計 2 和 3 的個數，其餘質因子乘積記為 `rest`
2. 若兩矩形 `rest` 不等 → 無解 (-1)
3. 計算總質因子數：矩形1 的 2總數 x₁, 3總數 y₁；矩形2 的 x₂, y₂
4. 目標：使兩矩形的 2總數相等、3總數相等
5. 操作數 = |x₁-x₂| + |y₁-y₂|（因每次操作改變一個質因子）
6. 實際修改邊長：優先在能整除的邊上操作

詳細步驟

// 分解函數
pair<int,int> count_23(long long x) {
    int c2 = 0, c3 = 0;
    while (x % 2 == 0) { x /= 2; c2++; }
    while (x % 3 == 0) { x /= 3; c3++; }
    return {c2, c3, x}; // 返回 (c2, c3, rest)
}

操作分配策略

需增加 2 的個數 → 對應矩形執行操作 2（÷3×2）
需減少 2 的個數 → 對應矩形執行操作 1（÷2）
需增加 3 的個數 → 不可能（操作只能減少 3）
需減少 3 的個數 → 執行操作 2（÷3×2），同時增加 2

完整 C++ 實現

#include <bits/stdc++.h>
using namespace std;

struct Rect {
    long long a, b;
    int c2, c3;
    long long rest;
};

Rect decompose(long long a, long long b) {
    Rect r; r.a = a; r.b = b;
    auto [c2a, c3a, rsta] = count_23(a);
    auto [c2b, c3b, rstb] = count_23(b);
    r.c2 = c2a + c2b;
    r.c3 = c3a + c3b;
    r.rest = rsta * rstb;
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long a1, b1, a2, b2;
    cin >> a1 >> b1 >> a2 >> b2;
    
    Rect r1 = decompose(a1, b1);
    Rect r2 = decompose(a2, b2);
    
    if (r1.rest != r2.rest) {
        cout << -1 << "\n";
        return 0;
    }
    
    int ops = 0;
    // 先平衡 3：將多的 3 轉為 2
    if (r1.c3 > r2.c3) {
        int d = r1.c3 - r2.c3;
        ops += d;
        r1.c3 -= d; r1.c2 += d;
    } else if (r2.c3 > r1.c3) {
        int d = r2.c3 - r1.c3;
        ops += d;
        r2.c3 -= d; r2.c2 += d;
    }
    // 再平衡 2：直接減少多的 2
    ops += abs(r1.c2 - r2.c2);
    
    // 實際修改邊長
    auto apply_ops = [&](Rect& r, int need_reduce_3, int need_reduce_2) {
        // need_reduce_3: 需要執行多少次 ÷3×2
        // need_reduce_2: 需要執行多少次 ÷2
        while (need_reduce_3 > 0) {
            if (r.a % 3 == 0) { r.a = r.a / 3 * 2; need_reduce_3--; }
            else if (r.b % 3 == 0) { r.b = r.b / 3 * 2; need_reduce_3--; }
        }
        while (need_reduce_2 > 0) {
            if (r.a % 2 == 0) { r.a /= 2; need_reduce_2--; }
            else if (r.b % 2 == 0) { r.b /= 2; need_reduce_2--; }
        }
    };
    
    int r1_reduce_3 = max(0, r1.c3 - r2.c3);
    int r2_reduce_3 = max(0, r2.c3 - r1.c3);
    int r1_reduce_2 = max(0, r1.c2 - r2.c2);
    int r2_reduce_2 = max(0, r2.c2 - r1.c2);
    
    apply_ops(r1, r1_reduce_3, r1_reduce_2);
    apply_ops(r2, r2_reduce_3, r2_reduce_2);
    
    cout << ops << "\n";
    cout << r1.a << " " << r1.b << "\n";
    cout << r2.a << " " << r2.b << "\n";
    return 0;
}

複雜度

• 質因子分解：O(log max(a,b))
• 其餘操作：O(1)
• 極快

關鍵點總結

1. 質因子 2,3 可操作，其他質因子不變 → 必須相等
2. 操作 2 實現「3→2」轉化，操作 1 實現「移除 2」
3. 平衡策略：先消除 3 的差異（轉為 2），再消除 2 的差異
4. 邊長修改：貪心優先在可整除的邊操作

此題展示了將操作問題轉化為質因子計數問題的經典數論建模技巧，化繁為簡。