2018HDU多校联赛第一场Maximum Multiple

我就是我 2022-05-19 10:04 171阅读 0赞

# 题目衔接：[http://acm.hdu.edu.cn/showproblem.php?pid=6298][http_acm.hdu.edu.cn_showproblem.php_pid_6298] #

# Maximum Multiple #

**Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 904    Accepted Submission(s): 421**

**Problem 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≤106), indicating the number of test cases. For each test case:  
The first line contains an integer n (1≤n≤106).

**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

**Source**

[2018 Multi-University Training Contest 1][]

### **题目大意：给你一个数，问你能不能找到3个数x，y，z，使得x+y+z=n且使得n能整除以x，n能整除以y,n能整除以z，如果有找出最大的x\*y\*z** ###

**思路：先打表，可以看出规律：能整除以3的都是n\*n\*n，能整除以4的都是n\*n\*（n\*2）；所以这就是规律**

**代码：**

#include<map>
    #include<stack>
    #include<queue>
    #include<cstdio>
    #include<string>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define maxn 100
    #define ll long long
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            ll n;
            ll ans=-1;
            scanf("%lld",&n);
            if(n%3==0)
            {
                n/=3;
                ans=n*n*n;
            }
            else if(n%4==0)
            {
                n/=4;
                ans=n*n*(n*2);
            }
            else
                ans=-1;
            printf("%lld\n",ans);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_6298]: http://acm.hdu.edu.cn/showproblem.php?pid=6298
[2018 Multi-University Training Contest 1]: http://acm.hdu.edu.cn/search.php?field=problem&key=2018+Multi-University+Training+Contest+1&source=1&searchmode=source