A16796. Honey Cake
编程题
普及-
知识点
题目描述
Hannah 和 Henry 要为包括他们自己在内的 $n$ 个人举办一场聚会。
他们为聚会购买了一个尺寸为 $w \times h \times d$ 英寸的蜂蜜蛋糕，想要将其等分成 $n$ 份。
蜂蜜蛋糕可以沿着任意一个面的方向切割。为保证切割的精确性，每条长度为 $w$ 的棱都要被切成相等且长度为整数的若干段；$h$ 和 $d$ 的棱也是同样要求。
给定蜂蜜蛋糕的尺寸，判断能否将其切成 $n$ 份等体积的部分。如果可以，请给出切割的方法。
他们为聚会购买了一个尺寸为 $w \times h \times d$ 英寸的蜂蜜蛋糕，想要将其等分成 $n$ 份。
蜂蜜蛋糕可以沿着任意一个面的方向切割。为保证切割的精确性，每条长度为 $w$ 的棱都要被切成相等且长度为整数的若干段；$h$ 和 $d$ 的棱也是同样要求。
给定蜂蜜蛋糕的尺寸，判断能否将其切成 $n$ 份等体积的部分。如果可以，请给出切割的方法。
输入格式
输入第一行包含三个整数 $w$，$h$ 和 $d$，表示蜂蜜蛋糕的三个维度，单位为英寸（$1 \le w, h, d \le 10^9$）。
输入第二行包含一个整数 $n$（$1 \le n \le 10^9$）。
输入第二行包含一个整数 $n$（$1 \le n \le 10^9$）。
输出格式
如果可以切割，请输出三个整数 $w_c$，$h_c$，$d_c$，分别表示在 $w$、$h$、$d$ 方向上所做的切割数。若无法切割，输出一个整数 $-1$。注意，每个维度上可以不切割，即允许切割数为 $0$。
输入输出样例
输入 #1
10 20 6 40
输出 #1
4 3 1
说明/提示
在第一个样例中，蛋糕将被切成 $5 \cdot 4 \cdot 2 = 40$ 个，每块尺寸为 $2 \times 5 \times 3$ 英寸。
