试题D：货物摆放

暴力法

/*
使用forfor枚举三种可能性i,j,k，且i<=j<=k，i*j*k==n
要注意两点：
1，for的边界判断for(LL j=i;i*j*j<=n;j++)：j的最大值就是sqrt(n/i)，因为j<=k && k==n/i/j
2，每次for后，必须要判断ijk能否被n整除！不能整除你索尼吗呢

在forfor的时候，考虑ijk的大小
但在累计res解的时候，ijk的位置不同代表了不同的解，所以要特判一下
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

int main()
{
    LL n = 2021041820210418;
    LL res = 0;

    for (LL i = 1; i * i * i <= n; i++)
        if (n % i == 0)  // 必须可以被整除
            for (LL j = i; i * j * j <= n; j++)
                if (n / i % j == 0)  // 写成(n%(i*j)==0)也不是不可以
                {
                    LL k = n / i / j;

                    if (i == j && j == k)       // ijk相等，只有ijk一个解
                        res++;
                    else if (i != j && j != k)  // ijk不等，有ijk,ikj,jik,jki,kij,kji六个解
                        res += 6;
                    else                        // i==j&&i!=k，有iik,iki,kii三个解
                        res += 3;
                }
    cout << res;
    return 0;
}

优化

/*
对于i*j*k==n，显然ijk都是n的约数/因数
所以先将n的所有约数找出来，比如6的是1236这样
再从中枚举ijk
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;

int main()
{
    LL n = 2021041820210418;
    vector<LL> vec;

    // 只需要枚举到sqrt(n)，sqrt(n)后面的直接用(n / i)
    for (LL i = 1; i * i <= n; i++)
        if (n % i == 0)
        {
            vec.push_back(i);

            if (n / i != i)  // 注意4的约数2和4/2是一个，不要重复统计
                vec.push_back(n / i);
        }

    int res = 0;
    int len = vec.size();
    for (int i = 0; i < len; i++)
        for (int j = 0; j < len; j++)
            for (int k = 0; k < len; k++)
                if (vec[i] * vec[j] * vec[k] == n)
                    res++;

    cout << res;
    return 0;
}