One day, N kids got one cake (a cylinder in shape). They decided to divide the cake so that everyone can have one piece of that cake. In the interest of fairness, pieces of the cake should be equal in size.
However, the kids had no knives to cut the cake. Luckily, Doraemon borrowed them a magic cake machine that can cut and clone cake.
To use Doraemon's cake machine, exactly M instructions must be entered. Otherwise the cake machine will destroy the cake (Doraemon's machines are not stable enough and have strange limits, you know).
For each instruction, the machine can perform one of the following actions:
- Cut the cake vertically. The cut should be perpendicular to the top surface, and is a diameter of the circle viewed from the top.
- Cut the cake horizontally. The cut should be parallel to the top surface.
- Clone a piece of cake. Due to a defect in design, the machine can not perform 'cut' action after any 'clone' action.
The two kinds of 'cut' actions are shown below:
The cake is always cutted as a whole. You can not cut just one or several pieces. For example, if you cut horizontally and then vertically, you always get 4 pieces.
A 'cut' action should make the cake into more pieces (i.e. you can not cut at a same position twice). Finally, there should be exactly N pieces of cake, which are in a same size. Thus each kid can get one and no pieces of cake are left.
Since the 'clone' action is extremely slow, use it as less as possible.
Input
This problem contains multi test cases.
The first line contains an integer T (0 ≤ T ≤ 2000), indicating the number of test cases.
Following T lines, each line contains one test case.
Each test case contains two integers N (1 ≤ N ≤ 6000000) and M (0 ≤ M ≤ 3000000), separated by one space, indicating there are N kids and M instructions should be used.
Output
For each case, output one integer R in one line, where R is the minimal number of 'clone' instructions. If exactly N pieces of cake can not be made from exactly M instructions, output -1 instead of R.
Sample Input
3 5 3 4 2 5 1
Sample Output
1 0 -1
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 using namespace std; 6 int main(void){ 7 int n, m, x, y, z, t; 8 #ifndef ONLINE_JUDGE 9 freopen("in", "r", stdin); 10 #endif 11 scanf("%d", &t); 12 while (t--){ 13 scanf("%d%d", &n, &m); 14 if (n - m <= 0) { 15 printf("-1\n"); continue; 16 } 17 if (n - m == 1){ 18 printf("0\n"); continue; 19 } //这种情况也要考虑一下…… 因为题目中没有说切的过程中需要等份地切。。 20 int min = 1<<30; // 坑！！ 21 for (int i = 0; i <= sqrt(n-m)+1; ++i){ 22 x = i; 23 if ((n-m-x)%(2*x-1) == 0){ 24 y = (n-m-x)/(2*x-1); 25 z = m - x - y; 26 if (min > z && z >= 0) min = z; 27 } 28 } 29 /* for (int i = 0; i <= sqrt(n-m) + 1; ++i){ 30 y = i; 31 if ((n-m+y)%(2*y+1) == 0){ 32 x = (n-m+y)/(2*y+1); z = m - x - y; 33 if (min > z && z >= 0) min = z; 34 } 35 } 36 */ if (min > m) printf("-1\n"); 37 else printf("%d\n", min); 38 } 39 return 0 ; 40 }
这道题目也太坑了……当初不知道切的过程中不一定要等份地切，只需要最后等份就可以了……次奥……
唉，还是怪自己，谁让自己没有注意数据范围捏，谁让自己没有想到可以暴力枚举捏，谁让自己还傻乎乎地以为这个题目是个遥远的数学题捏，谁让自己……那么二捏……
还有，设置 min 的值的时候，搞的不够大啊，然后WA了好几次啊，至于这么纠结么……以后学学人家，最小值的变量要初始化足够大，比如 0x3f3f3f3f
设竖着切 x 刀，横着切 y 刀，复制 z 次。
2 * x * (y + 1) + z = n
x + y + z = m
两个式子联立，可以得到 n - m = 2 * x * y + x - y = x * y + x + x * y - y >= x * y 所以呢，只需要枚举 x 或者 y 到 sqrt(n - m) 就可以了……是不是很快！
然后要考虑一种情况，就是 n == m + 1 的情况，这个时候，只需要横着切 m 刀，不用复制。
其实这是一道水题啊，为毛线自己没有做出来……
原因很简单，自己平时做题的时候都是做不出来的时候直接去翻人家的解题报告，看别人的代码去了，真正到自己写程序了，会出现各种错误，并且都是从来没有经历过的各种错误，也失去了独立思考问题的能力，以后要都自己做，可以看别人的代码，但是一定要自己独立思考一段时间，有自己的想法才可以，自己敲出来才知道自己经常的错误犯在哪里……然后以后真正比赛的时候，才能够发挥出正常水平，是不？