首页 > > 程序设计 > C/C++ >

HDU6298 Maximum Multiple （多校第一场1001）

2018-09-05 07:42:53来源：博客园阅读 ()

Maximum Multiple

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3241 Accepted Submission(s): 1344

Problem Description

Given an integer

Input

There are multiple test cases. The first line of input contains an integer

Output

For each test case, output an integer denoting the maximum

Sample Input

3 1 2 3

Sample Output

-1 -1 1

题目大意：n = x+ y + z, 需要满足 x|n, y|n, z|n (整除关系)，输出xyz的最大值，若不存在，输出-1

设 n/x = r n/y = s n/z = t ， r <= s <= t

所以1/r + 1/s + 1/t = 1

所以r <= 3

当r=3 s,t = (3,3)

当r=2 s,t = (4, 4) , (3, 6)

所以三种情况

n/3 n/3 n/3

n/2 n/4 n/4

n/2 n/3 n/6 (没有第一种大，舍去)

所以就判是否能整除3 或 4

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <string.h>
 5 #include <stdlib.h>
 6 #include <string>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <queue>
11 #include <algorithm>
12 #include <sstream>
13 #include <stack>
14 using namespace std;
15 #define rep(i,a,n) for (int i=a;i<n;i++)
16 #define per(i,a,n) for (int i=n-1;i>=a;i--)
17 #define pb push_back
18 #define mp make_pair
19 #define all(x) (x).begin(),(x).end()
20 #define fi first
21 #define se second
22 #define SZ(x) ((int)(x).size())
23 #define FO freopen("in.txt", "r", stdin)
24 #define lowbit(x) (x&-x)
25 #define mem(a,b) memset(a, b, sizeof(a))
26 typedef vector<int> VI;
27 typedef long long ll;
28 typedef pair<int,int> PII;
29 const ll mod=1000000007;
30 const int inf = 0x3f3f3f3f;
31 ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
32 ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
33 //head
34 int _, n;
35 int main() {
36     for(scanf("%d", &_);_;_--) {
37         scanf("%d", &n);
38         if(n%3 == 0) printf("%lld\n", 1ll * n * n * n / 27);
39         else if(n%4 == 0) printf("%lld\n", 1ll * n * n * n / 32);
40         else puts("-1");
41     }
42 }