转载自：https://www.lanqiao.cn/courses/5485

题目描述

小蓝有一个超大的仓库，可以摆放很多货物。

现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。

小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物,满足 n = L W H。

给定 n，请问有多少种堆放货物的方案满足要求。

例如，当 n = 4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2 × 2 × 1、4 × 1 × 1。

请问，当 n = 2021041820210418 （注意有 16 位数字）时，总共有多少种方案？

提示：建议使用计算机编程解决问题。

题目大意

给定一个 n，n=2021041820210418，问满足 (a,b,c)=n 的(a,b,c)​ 组合有多少种。

解题思路

首先明确，(a,b,c)肯定是 n的因子（n = a bc && n=b ac && n=c * ab)

于是可以筛出 n 的因子，存入数组中。

我们得到 n 的因子数为 128，数目很小，所以可以直接枚举 a,b,c，来计算总共的组合数。

最终答案：2430

代码:

#include<bits/stdc++.h>
using namespace std;
int const maxn=1e5+10;
//存放因子的数组 
long long factor[maxn];
int main(){
    long long n=2021041820210418;
    int len=0;
    //只要遍历到 根号n 就可以了 
    for(long long i=1;i*i<=n;i++){
        //如果 一个数可以被 n整除 那么这个数就是n的因子 
        if(n%i==0){
            factor[len++]=i;
            // n/i  的结果就是另一个因子 这个数*i=n 也就是为什么只要遍历到根号n就可以了
            // 如果 i*i=n话  i就会被记录两次,所以加个条件 (n/i)!=i
            if((n/i)!=i){
                factor[len++]=n/i;
            }
        }   
    }

    int count=0;
    for(int i=0;i<len;i++){
        for(int j=0;j<len;j++){
            //有个优化,如果前两个数的乘积已经大于n了,第三个数就没必要乘了
            if(factor[i]*factor[j]>n) {
                continue;
            }
            for(int k=0;k<len;k++){
                if(factor[i]*factor[j]*factor[k]==n){
                    count++;
                }
            }
        }
    } 
    cout << count;
}