P1002 a+b+c

一定都是的质因子乘积的组合
考虑把进行质因数分解 然后把质因数分配给
因为 所以最多有不超过25个因子
比如有个2 我们枚举有个 有个
那么不同的分配方式是

先对进行质因数分解 然后维护好每一种因子的个数
总的复杂度

TO验题人:
实际上本机测试这题数据出到1e9都没问题
但是牛客验题机波动问题 就算数据缩小到1e7了 测试点8,9,16还是一直抖动
跑下来的一会5ms 一会1001ms超时 体验极差
如果这个问题解决了 可以再加强数据

class Solution {
public:
    /**
     * 
     * @param n int整型 n
     * @return int整型
     */
    int aa[50];
    int bb[50];
    int ans, cnt;
    void dfs(int dep, int a, int b, int c) {
        //if(a + b + c > ans) return;  //可以剪枝
        if(dep > cnt) {
            ans = min(ans, a + b + c);
            return;
        }
        for(int i = 0; i <= bb[dep]; i++) 
            for(int j = 0; i + j <= bb[dep]; j++) {
                int ta = 1, tb = 1, tc = 1;
                for(int k = 1; k <= i; k++) ta *= aa[dep];
                for(int k = 1; k <= j; k++) tb *= aa[dep];
                for(int k = 1; k <= bb[dep] - i - j; k++) tc *= aa[dep];
                dfs(dep + 1, a * ta, b * tb, c * tc);
            }
    }
    int solve(int n) {
        // write code here
        ans = n + 5;
        cnt = 0;
        for(int i = 2; i * i <= n; i++) {
            if(n % i == 0) aa[++cnt] = i;
            while(n % i == 0) {
                n /= i;
                bb[cnt]++;
           }
        }
        if(n != 1) aa[++cnt] = n, bb[cnt] = 1;
        dfs(1, 1, 1, 1);
        return ans;
    }
};