hdu - 6298

Posted by WildCow on July 23, 2018

Maximum Multiple

Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

Description

Given an integer $n$, Chiaki would like to find three positive integers $x$, $y$ and $z$ such that: $n=x+y+z, x∣n, y∣n, z∣n$ and $xyz$ is maximum.

Input

There are multiple test cases. The first line of input contains an integer $T (1≤T≤10^6)$, indicating the number of test cases. For each test case: The first line contains an integer $n (1≤n≤10^6)$.

Output

For each test case, output an integer denoting the maximum $xyz$. If there no such integers, output −1 instead.

Sample Input

3
1
2
3

Sample Output

-1
-1
1


给你一个 $n$,你要找 $n$ 的三个因子 $x,y,z$(可以相同),然后最大化他们的乘积
我们设 $x = \frac{n}{a},y = \frac{n}{b},z = \frac{n}{c}$
那么我们可以把这个式子表示成 $n=\frac{n}{a} + \frac{n}{b} + \frac{n}{c}$
简单化简一下就是 $1=\frac{1}{a} + \frac{1}{b} + \frac{1}{c}$
杜教说 这组不定方程只有三组解 {3, 3, 3}, {2, 4, 4}, {6, 2, 3}
感性认知了一下觉得很对
下面是证明

我们先设 $a≤b≤c$
显然 a b c 中不可能有 1
又显然 a b c 中不可能有两个 2
然后我们考虑当 $c = 6$ 时
很显然对应的只有 $a = 2, b = 3$
而当 $c \geq 6$ 时
我们会发现若要满足等式
需要 $a, b$ 再尽可能地小
但是当 $c = 6$ 的时候 a b 的大小已达到下限
所以有 $c \leq 6$
简单枚举一下就会发现只有 3 组解
证毕

又如果满足 {6, 2, 3}
那么 {3, 3, 3} 肯定也满足而显然 {3, 3, 3} 比 {6, 2, 3} 更优
所以只要取 {3, 3, 3}, {2, 4, 4} 比较一下大小就好了


#include <bits/stdc++.h>
#define LL long long
using namespace std;

int main(int argc, char const *argv[])
{
    int ncase;

    scanf("%d", &ncase);
    while(ncase --){
        int x;
        LL a, b;
    
        a = b = -1;
        scanf("%d", &x);
        if(x % 3 == 0){
            a = 1ll * x / 3 * x / 3 * x / 3;
        }
        if(x % 4 == 0){
            b = 1ll * x / 4 * x / 4 * x / 2;
        }
        printf("%lld\n", max(a, b));
    }
    
    return 0;
}