n = a * b * c 题解 by Aze

1.题意

输入一个整型数据 n，拆分成三个因子相乘的形式 a * b * c，且 1 <= a <= b <= c <n，在所有符合要求的 abc 中输出 c-a 最小且 a 最小的结果

2.分析（copy李哥的思路）

想要求得abc，很容易想到通过三个for循环 a b c 依次从 2 枚举到 n

可是这样必定超时，所以我们需要缩小枚举范围，优化算法

假设 n = 12

先确定 a 的值

因为 1 <= a <= b <= c <n，而 n = a * b *c

所以 abc 取值最小的是 a * a * a

for (int i = 2; i * i * i <= n; i++)
// 为什么i初始化为2：因为 abc 取值大于1
// i * i * i <= n怎么理解：
//  当 <n 时说明 三个数全取 a 的话 a*a*a 不够n，后面 b 或 c 要大于 a 
//  若使用 i < n 来做，有很多数是没必要用的，比如 11 10 9 8 7等等，会极大的增加时间复杂度
//  数小看不太出来，如果是100000这么大的呢，效果显而易见

当然得保证 i 是n的因子

if (n % i == 0)
// 如 12 % 2 == 0，12除以2没有余数说明2是12的因子

结合一下，我们就能枚举出所有 a 的取值

for(int i = 2; i * i * i <= n; i++)
{
	if(n % i == 0)
	{
	}
}

同样，对于 b，我们既然已经算出 a 的值，那就可以在 n 中除去 a，以便更容易的算出 b

int x = n / a
for (int j = i; j * j <= x; j++)

b 枚举出来之后，还需要一个循环来枚举c吗？很显然，没必要

x / j == c
// 12  = a *  b * c 去掉 a = 2 后 x = 6，即 x = b * c，除去 b 便是 c 的值

结合一下，再加上对 b 是否因子的判断

for(int j = i; j * j <= x; j++)
{
	if( x % j == 0)
}
// 需要加对c是否为因子的判断吗？ (x / j) % (x / j) ==0 ? 很显然没必要

至此，我们已经能枚举出所有结果

for(int i = 2; i * i * i <= n; i++)
{
	if(n % i == 0)
	{
        for(int j = i; j * j <= x; j++)
        {
            if( x % j == 0)
            {
                a = i;
                b = j;
                c = x / j;
            }
        }
	}
}

接下来筛选出符合要求的结果并输出

c - a == x / j - i
// 需要保证 其为最小的一个
int temp = 100000; // 声明一个非常大的变量，确保第一次比较能成功
if(x / j - 1 < temp) // 如果当前的结果中 c - a 小于之前结果中的 c - a，则将当前结果置为最终结果 
{
    temp = x / j - i;
    a = i;
    b = j;
    c = x / j;
}
// 至于 a 最小，因为我们是从 a 开始从小到大枚举，所以当满足 c - a 最小时，a 肯定小

现在将其重新组合进去，加上输出判定

for(int i = 2; i * i * i <= n; i++)
{
    int a,b,c,temp = 100000;
	if(n % i == 0)
	{
        for(int j = i; j * j <= x; j++)
        {
            if( x % j == 0 && x / j - i < temp)
            {
                temp = x / j - i;
                a = i;
                b = j;
                c = x / j;
            }
        }
	}
}
if(temp == 100000) printf("No solution\n");// 如果temp没变说明一个结果都没有
else printf("%lld=%d*%d*%d",n,a,b,c);

至此，问题解决！补充一些细节：

#include <cstdio> // 等价于 stdio.h
typedef long long LL; // 等价于 #define LL long long 
const int MAX = 100020; // 等价于 #define MAX 100020
int main()
{
	LL n;
	int count;
	scanf("%d", &count);
	while (count--)
	{
		scanf("%lld", &n);
		int a, b, c, temp = MAX;
		for (int i = 2; i * i * i <= n; i++)
		{
			if (n % i == 0)
			{
				int x = n / i;
				for (int j = i; j * j <= x; j++)
				{
					if (x % j == 0 && x / j - i < temp)
					{
						temp = x / j - i;
						a = i;
						b = j;
						c = x / j;
					}
				}
			}
		}
		if (temp == MAX)
		{
			printf("No solution\n");
			continue;
		}
		else
		{
			printf("%lld=%d*%d*%d", n, a, b, c);
		}
	}
}

讲完！

题解 | #n=a*b*c#

n = a * b * c 题解 by Aze

1.题意

2.分析（copy李哥的思路）

题解 | #n=abc#