Sgu/126

数学解法

一个二进制的数学题，证明详见：http://damselfly.diandian.com/post/2011-10-25/6203890

#include <stdio.h>
using namespace std;
 
int a, b;
 
int gcd(int a, int b)
{
    int c;
    while (c = a % b)
          a = b, b = c;
    return b;
}
 
int main()
{
    scanf("%d %d", &a, &b);
    if (!a || !b) {
       printf("0");
       return 0;
    }
    int s = (a + b) / gcd(a, b), res = 0;
    while (!(s & 1)) 
    {
          s /= 2;
          res++;
    }
    if (s == 1) printf("%d", res);
       else     printf("-1");    
    return 0;
}
// From FingerSed

模拟解法

首先我们需要知道，求 A,B 的步数其实就等同于求 A/gcd(A,B),B/gcd(A,B) 的步数。

对于这个的证明很明显，每次移动的求一定是 gcd(A,B) 的倍数。

对于每次移动，令 A = A/gcd(A,B) ,B = B/gcd(A,B)，讨论情况 ：

（1） A，B都为偶数（不可能）

（2） A，B有一个为奇数 （无解，很明显吧，因为A+B都是奇数了）

（3） A，B都是奇数-> 假设A是较小的那一个，那么就可以变化为 A*2,B-A ，然后我们的新目标就变成了求解 A*2,B-A 的步数

结束条件 A=0 或 B=0

容易证明，上述步骤重复次数最多不超过 log(A+B)次

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
	if(b!=0) return gcd(b,a%b);
	return a;
}
int A0,B0;
int solve(int A,int B)
{
	if(!A||!B) return 0;
	int t=gcd(A,B);
	A/=t;B/=t;
	if(!(A%2==1&&B%2==1)) return -1;
	if(A>B) swap(A,B);
	t=solve(A*2,B-A);
	return t==-1?-1:t+1;
}
int main()
{
	cin>>A0>>B0;
	cout<<solve(A0,B0);
	return 0;
}