Maximum Multiple

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

Total Submission(s): 3985    Accepted Submission(s): 926

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

 

题意：给定一个正整数n，满足n=x+y+z, 并且x , y , z能整除n,求满足条件的x,y,z的max(x,y,z)

 

分析: 首先理解整数

1分成三个分子为

1的分数和，仅有两种（1/3,1/3,1/3），（1/2,1/4,1/4）

所以要将n分解成三份并且能整除的话就只能分成（n/3,n/3,n/3）,(n/2,n/4,n/4)

 

只需要判断n能不能被3或者4整除

 

1 #include 
       
         2 using namespace std; 3  4 int t; 5 long long n; 6  7 int main() 8 { 9     scanf("%d",&t);10     while(t--) {11         scanf("%d",&n);12         if(n%3 == 0) {13             printf("%lld\n",n/3*n/3*n/3);14         } else if(n%4 == 0) {15             printf("%lld\n",n/2*n/4*n/4);16         } else {17             printf("-1\n");18         }19     }20     21     return 0;22 }