一、题目
Given an integer $n$, Chiaki would like to find three positive integers $x$, $y$ and $z$ such that: $n=x+y+z$, $xmid n$, $y mid n$, $z mid n$ and $xyz$ is maximum.
InputThere are multiple test cases. The first line of input contains an integer $T$ ($1 le T le 10^6$), indicating the number of test cases. For each test case: The first line contains an integer $n$ ($1 le n le 10^{6}$).
OutputFor each test case, output an integer denoting the maximum $xyz$. If there no such integers, output $-1$ instead.
Sample Input
3 1 2 3Sample Output
-1 -1 1
二、分析
需要先按照题意分析(20项即可),然后发现能输出答案的都是3或者4的倍数,那么x,y,z的结构就是1+1+1和1+1+2的模式,如果出现3和4的公倍数,为了能保证xyz的更大值,优先考虑1+1+1的结构。
三、代码
#include <iostream> #include <cstdio> using namespace std; typedef long long LL; LL Max(const LL a, const LL b) { return a>b?a:b; } /*** 找规律代码 ***/ void solve(int N) { LL ans = -1; for(int i = 1; i < N; i++) { for(int j = 1; j < N; j++) { for(int k = 1; k < N; k++) { if(N%i == 0 && N%j == 0 && N%k == 0 && N == i+j+k) { ans = Max(i*j*k, ans); } } } } cout << ans <<endl; } int main() { int T, N; LL ans; scanf("%d", &T); while(T--) { scanf("%d", &N); if(N%3==0) { ans = (LL)(N/3)*(N/3)*(N/3); printf("%I64d ", ans); } else if(N%4==0) { ans = (LL)(N/4)*(N/4)*(N/2); printf("%I64d ", ans); } else printf("-1 "); } return 0; }