CF267A 【Subtractions】

题目大意：

给你两个数 \(a\) , \(b\) ( \(a\) , \(b\) \(\le\) \(10^9\) )，每次用大的减去小的，问当某个数为 \(0\) 时，一共减了多少次。

思路：

假设 \(a\) 为大的数，\(b\) 为小的数，且两数相差很大
那么 \(a\) 最后可能会变成 \(a-b-b-...-b\)
将 \(-b-b-...-b\) 合并，就可以得到 \(- k \times b(k\times b \le a\) 且 \(a-k\times b < b)\)
这个 \(k\) 其实就是 \(a\) 整除 \(b\) 的结果 。
所以
\(a-b-b-...-b = a-k \times b = a-(\lfloor \frac{a}{b} \rfloor)\times b = a\mod b\)
所以每次 \(a\) 最终都会变成 \(a\mod b\)，变化次数即 \(\lfloor \frac{a}{b} \rfloor\)
可以用类似 \(\gcd\) 的辗转相除法来完成。
复杂度和 \(\gcd\) 一样，都是 \(O(\log n)\) 的。

Code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<bitset>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define LL long long

using namespace std;

LL read()
{
	LL ans=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
	return ans*f;
}

int n,a,b;

inline int get(int x,int y);

int main()
{
	n=read();
	while(n--)
	{
		a=read();b=read();
		printf("%d\n",get(a,b));
	}
	return 0;
}

//用类似 gcd 的辗转相除法
//x 为大数，y 为小数
//如果刚开始 x < y ，那么在一次操作后，x 与 y 将互换
inline int get(int x,int y)
{
	if(!y)  如果小的数为 0 ，那么操作已经完成，返回 0
		return 0;
	// 否则将大数设为 y ，小数设为 x % y ( y > x % y )
	// 并把变化次数 x / y 加入答案
	return get(y,x%y)+x/y;
}