原始题目

Maximum Multiple

• Time Limit: 4000/2000 MS (Java/Others)
  
• Memory Limit: 32768/32768 K (Java/Others)
• Total Submission(s): 1503
  
• Accepted Submission(s): 653

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

Recommend

liuyiding

题目大意

已知三个数的和为\(n\)，且三个数均能整除\(n\)，求三个数乘积的最大值。

解题思路

数论问题

不妨设\(a=\frac{n}{x},b=\frac{n}{y},c=\frac{n}{z}\)。 由题目条件可以得到 \[$\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=1\]$ 由于\(a,b,c\)均为整数（正整数）。 所以该方程共有三组解。 分别为\(a=3,b=3,c=3,xyz=\frac{n^3}{27}\)或者\(a=2,b=4,c=4,xyz=\frac{n^3}{32}\)或者\(a=2,b=3,c=6,xyz=\frac{n^3}{36}\)

故判断\(n|3,n|4\)整除即可。又因为若第三组解成立，则必有第三组解，而且第一组解对应的\(xyz\)值更大，故不考虑第三组。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size()) 
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int maxn=1e5+5;


ll t,n,m;

int main(){
	ios::sync_with_stdio(false);
	cin>>t;
	
	while(t--){
		cin>>n;
		if(!(n%3)) cout<<1ll*n*n*n/27<<endl;
		else if(!(n%4)) cout<<1ll*n*n*n/32<<endl;
		else cout<<"-1"<<endl;
	}
	
} 

收获与反思

• 寻找条件的关系
• 数论学习