10 3 1

【题目描述】
电容，符号是 C，单位是法拉（F） ，但是这个单位太大了，Jerry 会用皮法（pF）来
表达一个电容pF=10
?12
F。Jerry 告诉你：两个容量是 C1 和 C2 并联的电容会形成一个
新的容量为C1 C2电容；两个容量 C1 和 C2 电容串联将形成一个新的容量
1
1
C1

1
C2
电容。由于技术原因，Jerry 每次只能在原来的基础上合并一个 1pF 电容器或串上一个
1pF 电容器，而不是两个后串在一起。Jerry 练习需要几个容量 1pF 的
电容构成一个容量
a
?
pF 的电容。 Jerry 手头的 1pF 电容器不多， 他要求你尽可能少地使用它。 1pF
电容器来完成任务，告诉他至少要用多少个。
输入格式
一行正整数 T，表示题目数量。
之后 T 每行两个正整数 a 和 b，这个问题要求的电容量是
?
?
pF。
输出格式
共 T 行，每行一个整数，说明完成这个问题至少需要使用 1pF 电容个数。
【输入样例 1】
2
1 1
3 2
【输出样例 1】
1
3
【输入样例 2】
2
6 5
199 200
【输出样例 2】
6
200
数据规模与约定
对于 20%的数据，1≤a≤10，1≤b≤10。
对于另外 20%的数据，a=1。
对于另外 20%的数据，b=1。
对于 100%的数据，1≤a≤10
18
，1≤b≤10
18
，1≤T≤5000。

题解：

直接用辗转相去统计个数

#include
using namespace std;

#define fucki(x) scanf("%d",&x)
#define lfucki(x) scanf("%lld",&x)
#define fucko(x) printf("%d",x)
#define lfucko(x) printf("%lld",x)
#define ll long long
#define ent putchar('\n')
#define kong putchar(' ')
#define fo(i,j,k) for(int i=j;i<=k;i )

ll gcd(ll a,ll b)
{
if(!b) return a;

return gcd(b,a%b);

}

int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int t;
cin>>t;

while(t--)
{
ll a,b;
// cin>>a>>b;
lfucki(a);
lfucki(b);

ll c = gcd(a,b);
a/=c;
b/=c;

ll ans = 0;
while(a&&b)
{
if(a>b)
{
ans = (a/b);
a %= b;
}
else {
swap(a,b);

ans = (a/b);
a %= b;
}
}

lfucko(ans);
ent;
}
return 0;
}