[枚举]Stormwind 2022杭电多校第8场 1011

Problem Description

\space \space  "So, people of Stormwind! Let us unite this day. Let us renew our promise to uphold and protect the Light, and together we will face down this dark new storm and stand firm against it—as humanity always has… and humanity always will!"

\space \space  The crowd saved its greatest roars for the end. A chorus of "Long live King Varian! Long live King Varian!" rose into the sky with vigor and conviction. The cheers were unending, echoing deep into Elwynn Forest and faintly reaching even the distant peaks of the Redridge Mountains.

Varian Wrynn gained a rectangular piece of gold in the battle, with length nn and width mm. Now he wants to draw some lines on the gold, so that later he can cut the gold along the lines.

The lines he draws should satisfy the following requirements:

1. The endpoints of the lines should be on the boundary of the gold.
2. The lines should be parallel to at least one boundary of the gold.
3. After cutting along all the lines, each piece of gold is a rectangle with integer length and width.
4. After cutting along all the lines, the area of each piece of gold should be at least kk.
5. Two lines should not share more than one common points.

Varian Wrynn wants to cut the gold in such a way that maximizes the lines he draws.

As Alliance's Supreme King, he certainly doesn't have time to do this. So he finds you! Please help him to cut the gold!

Input

The input consists of multiple test cases.

The first line contains an integer T\ (1\leq T \leq 100)T (1≤T≤100) indicating the number of test cases.

Each test case consists of one line containing three integers n, m, k\ (1\leq n,m,k \leq 10^5)n,m,k (1≤n,m,k≤105). Its guaranteed that n\times m \geq kn×m≥k.

Output

For each test case, output one line containing one integer, the maximum number of lines you can draw.

Sample Input

2

5 4 2

10 9 13

Sample Output

5

4

Hint

In the first test case, Varian Wrynn can draw 4 lines parallel to the boundary of length 4 and 1 line parrallel to the boundary of length 5. After cutting along the lines, he can get 10 pieces of gold of size 2.

题意： 给出一块n*m的矩形，要求画出若干条横竖的线，使得按照这些线进行切割后得到的每块矩形面积都大于等于k，问最多能画几条线。

分析： 当确定了某方向上的间隔后，可以O(1)求出另一个方向上最优的间隔，所以可以O(n)枚举一个方向上的间隔，设为x，那么另一个方向上的间隔就是ceil(k/x)，ceil表示上取整，当得到了两方向的间隔后就可以算出来画线数了，若间隔为x，那么这个方向上的画线数就是floor(n/x)-1，floor表示下取整，两方向统计出来加和就是答案。

具体代码如下：

#include 
using namespace std;
 
signed main(){
	int T;
	cin >> T;
	while(T--){
		int n, m, k;
		cin >> n >> m >> k;
		int ans = 0;
		for(int i = 1; i <= min(n, k); i++){
			int res = floor(1.0*n/i)-1;
			int t = ceil(1.0*k/i);
			if(t > m) continue;
			res += floor(1.0*m/t)-1;
			ans = max(ans, res);
		}
		cout << ans << endl;
	}
}