【题目描述】 电容，符号是 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<bits/stdc .h> 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; }