最大公约数的最小公倍数【题解】

经验分享区
1

解题思路

本题可以使用动态规划（DP）的方法来解决。核心思想是通过遍历每个卡包，记录所有可能的红色盒子和蓝色盒子的最大公因数组合，最后找出这些组合中最小公倍数的最大值。

1. 定义状态

使用一个二维的 unordered_map 来存储状态，dp[red_gcd][blue_gcd] 表示红色盒子的最大公因数为 red_gcd，蓝色盒子的最大公因数为 blue_gcd 的状态是否可达。初始时，dp[0][0] = 1，表示两个盒子初始为空的状态是可达的。

2. 状态转移

对于每个卡包，有两种分配方式：

  • 将 a[i] 放入红色盒子，b[i] 放入蓝色盒子。此时新的红色盒子最大公因数为 gcd(red_gcd, a[i])，新的蓝色盒子最大公因数为 gcd(blue_gcd, b[i])。
  • 将 b[i] 放入红色盒子 ，a[i] 放入蓝色盒子。此时新的红色盒子最大公因数为 gcd(red_gcd, b[i])，新的蓝色盒子最大公因数为 gcd(blue_gcd, a[i])。

3. 最终结果

遍历所有可达的状态，计算每个状态下红色盒子和蓝色盒子最大公因数的最小公倍数，取其中的最大值作为最终结果。

拿下！

        for(auto& red:dp){
            for(auto& blue:red.second){
                long long red_gcd=red.first;
                long long blue_gcd=blue.first;
                long long s11=gcd(red_gcd,a[i]);
                long long s12=gcd(blue_gcd,b[i]);
                dpp[s11][s12]=1;
                long long s21=gcd(red_gcd,b[i]);
                long long s22=gcd(blue_gcd,a[i]);
                dpp[s21][s22]=1;
            }
        }
2 个赞