小A想要合成一个化合物。初始时,容器里有 a 克的物质A。小A每次操作都会向容器中加入 b 克物质A与 c 克物质B,当容器中物质A与物质B的比值不大于 d 时,说明小A合成成功了.
前 3 个测试点满足
1≤a,b,c,d≤105
后 2 个测试点满足
1≤a,b,c,d≤109
输入格式:
输入 4 个整数a, b, c, d.
输出格式:
若可以合成化合物,那么输出小A的最小操作次数,否则输出−1
输入样例1:
1 | 5 2 3 2 |
输出样例1:
进行 1 次操作后,容器里有 7 克物质A与3 克物质B, 此时 7/3>2, 不满足条件,2次操作后,容器里有 9 克物质A与6 克物质B, 此时 9/6<=2 满足条件,因此答案为 2.
1 | 2 |
输入样例2:
1 | 6 9 2 3 |
输出样例2:
1 | -1 |
输入样例3:
1 | 100000 99999 100000 1 |
输出样例3:
1 | 100000 |
思路
直接暴力循环求解会超时,得不到满分
设x为某时物质A的质量,y为某时物质B的质量,操作n次后满足条件,即满足(a+b*n)/c*n <= d,根据该公式推导出n的解公式即可
代码
1 |
|