AtCoder Regular Contest 159

B - GCD Subtraction

1. 问题：每次A,B都减去gcd(A,B)，求其中一个减到0至少需要多少次
2. 主要思路：
   1. 首先第一步应该想到每次减去的数，先减去的数一定是后减去的数的因子，可以直接将A/gcd(A,B),B/gcd(A,B)，计算两个互质数的答案
   2. gcd(A,B)=1，考虑什么时候不再减去1，假设为d,那么有 d|(A-t),d|(B-t),于是有 $A=i\ast d+t$,$B=j\ast d+t$，$1\le t<d$, d有以下性质
      $$d是质数且d|(A-B)$$
   3. 每次求$A-B$的所有质因子

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){return b ==0?a:gcd(b,a%b);
} 
void get(LL a,LL b,LL &ans) {if(a == 0 ||b == 0) return ;if(a > b) swap(a,b);LL _min = a;LL d = a;LL t = abs(a-b);LL tmp = t;vector<LL> prime;for(LL i = 2;i * i <= tmp; ++i) {if(t %i == 0) {prime.push_back(i);while(t%i==0) t/= i;}}if(t > 1) prime.push_back(t);for(auto &c:prime) {if(a > c &&a%c < _min) {_min = a%c;d = c;}}ans += _min;get((a-_min)/d,(b-_min)/d,ans);
}
int main(void) {LL A,B;cin>>A>>B;LL d = gcd(A,B);A = A/d;B = B/d;LL ans = 0;get(A,B,ans);cout<<ans<<endl;return 0;
}