Problem Description
When people drink some tea in the teahouse, they also play some casual games. Now, inverting cups is a popular game. The meaning of the question is, now there are some cups which are upturned, we can regard the total number of the cups as a positive integer
number A , and we can invert some cups, the number is B and B is also a positive integer number. We define one retroflexion that if the original cup is upturned, one retroflexion makes it downward, and if the original cup is downward, one retroflexion makes
it upturned. So the question is if the whole original cups are upturned , can we invert these cups to make all the cups downward? And if it is possible, how many is the least of times?
number A , and we can invert some cups, the number is B and B is also a positive integer number. We define one retroflexion that if the original cup is upturned, one retroflexion makes it downward, and if the original cup is downward, one retroflexion makes
it upturned. So the question is if the whole original cups are upturned , can we invert these cups to make all the cups downward? And if it is possible, how many is the least of times?
Input
The input contains multiple test cases(cases<=100000). Each case one line given two numbers , the first integer A (1<=A<=2^63) and the second integer B (1<=B<=A). The input is terminated by the end of file.
Output
For each test case, you should output how many the least of times if it is possible for us to invert all the cups, and if it is impossible please output “No Solution!”
Sample Input
5 3 14 4 8 5 11 4
Sample Output
3 4 4 No Solution!
//
#include<iostream>
#include<cstdio>
using namespace std;
int main() {
__int64 a, b, t, ans;
while (scanf("%I64d%I64d",&a,&b)==2) {
ans = 0;
if (a % 2 && b % 2 == 0) {
printf("No Solution!\n");
continue;
}
while (1) {
if (a / b >= 3) {
t = (a-2*b)/b;
ans += t;
a -= t*b;
}
if (a % b == 0)ans += a / b;
else if (a % 2 == b % 2)ans += 3;
else if (a / b >= 2)ans += 4;
else {
b = a - b;
continue;
}
break;
}
printf("%I64d\n", ans);
}
return 0;
}