2018HDU多校训练一 A - Maximum Multiple

Given an integer nn, Chiaki would like to find three positive integers xx, yy and zzsuch that: n=x+y+zn=x+y+z, x∣nx∣n, y∣ny∣n, z∣nz∣n and xyzxyz is maximum.

Input

There are multiple test cases. The first line of input contains an integer TT (1≤T≤1061≤T≤106), indicating the number of test cases. For each test case:

The first line contains an integer nn (1≤n≤1061≤n≤106).

Output

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

Sample Input

Sample Output

-1

-1

1

题意：给你一个整数n,3个整数 x,y,z.让你求满足 n=x+y+z,x*y*z的最大值；

令 a=n/x ,b=n/y, c=n/z, 则1/a+1/b+1/c=1;且a,b,c为正整数,则a,b,c可取 3 3 3,2 4 4； 2 3 6；

2 3 6的话没有取没有3 3 3大，故这个可以省去，就剩下 3 3 3； 2 4 4；先考虑是否可以被3整除，再考虑是否可以被4整除，以为3 个数和一定能话，相等时乘积最大，都不满足输出-1,都满足输出 3 3 3一组；

参考代码为：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()

{

	ios::sync_with_stdio(false);

	cin.tie(0);

	LL T,n,x,y,z,sum;

	cin>>T;

	while(T--)

	{

		cin>>n;

		if((n%3)==0)

		{

			x=y=z=n/3;

			sum=x*y*z;

			if(x+y+z==n) cout<<sum<<endl;

			else cout<<-1<<endl;

		}

		else if((n%4)==0)

		{

			x=y=n/4,z=n/2;

			sum=x*y*z;

			if(x+y+z==n) cout<<sum<<endl;

			else cout<<-1<<endl;

		}

		else cout<<-1<<endl;

	}

	return 0;

 }

巴特西

2018HDU多校训练一 A - Maximum Multiple

最新文章

热门文章