HDU6298 Maximum Multiple (多校第一场1001)
2024-10-19 21:39:01
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 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).
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
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
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
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 all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define FO freopen("in.txt", "r", stdin)
#define lowbit(x) (x&-x)
#define mem(a,b) memset(a, b, sizeof(a))
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=;
const int inf = 0x3f3f3f3f;
ll powmod(ll a,ll b) {ll res=;a%=mod;for(;b;b>>=){if(b&)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//head
int _, n;
int main() {
for(scanf("%d", &_);_;_--) {
scanf("%d", &n);
if(n% == ) printf("%lld\n", 1ll * n * n * n / );
else if(n% == ) printf("%lld\n", 1ll * n * n * n / );
else puts("-1");
}
}
最新文章
- 461. Hamming Distance and 477. Total Hamming Distance in Python
- 对只转发结果集的无效操作 first
- linux进程用户内存空间和内核空间
- mysql的小知识点(关于数据库的导入导出 对于windows)
- 3[doses] ------一种诡异的写法
- Ubuntu中文输入法的安装
- Python学习入门基础教程(learning Python)--5.1 Python下文件处理基本过程
- Netty4.x中文教程系列(一) Hello World !
- EF一次请求公用一个实例
- iOS6和iOS7适应代码(6) —— NSLocalizedString
- Bootstrap 使用清单组组件创建价格表
- 安装Appium
- ThinkPHP中对系统常量的使用
- srand()和rand()函数的使用
- Python内置函数(22)——list
- JavaScript 散集合(HashArray)
- Android为TV端助力 eclipse build project 出现major.minor version 52.0的问题
- Flask WTForms的使用和源码分析 —— (7)
- nginx开机启动
- Uncaught InvalidStateError: Failed to set the &#39;value&#39; property on &#39;HTMLInputElement&#39;: This input element accepts a filename, which may only be programmatically set to the empty string.
热门文章
- nfs cron shell 笔记
- 如何设置linux在出现kernel panic后自动重启 (ZT)
- Android 4学习(6):概述 - 深入了解Android Activity
- 清空select标签中option选项的4种不同方式
- 链接ssh失败问题
- Github修改项目显示的语言类型
- to_date() 、to_char()、to_number的FMT格式
- strcmp()比较函数和strcasecmp()和strnatcmp()
- go install 命令
- C++面向对象类的实例题目三