网站建设工作下步打算,计算机前端,企业网站建设方案价位,小程序公众号网站建设文章目录 AtCoder Regular Contest 159B - GCD Subtraction AtCoder Regular Contest 159
B - GCD Subtraction
问题#xff1a;每次A,B都减去gcd(A,B)#xff0c;求其中一个减到0至少需要多少次主要思路#xff1a; 首先第一步应该想到每次减去的数#xff0c;先减去的数… 文章目录 AtCoder Regular Contest 159B - GCD Subtraction AtCoder Regular Contest 159
B - GCD Subtraction
问题每次A,B都减去gcd(A,B)求其中一个减到0至少需要多少次主要思路 首先第一步应该想到每次减去的数先减去的数一定是后减去的数的因子可以直接将A/gcd(A,B),B/gcd(A,B)计算两个互质数的答案gcd(A,B)1考虑什么时候不再减去1假设为d,那么有 d|(A-t),d|(B-t),于是有 A i ∗ d t A i*dt Ai∗dt, B j ∗ d t B j*dt Bj∗dt 1 ≤ t d 1\le t d 1≤td, d有以下性质 d 是质数且 d ∣ ( A − B ) d 是质数 且 d| (A-B) d是质数且d∣(A−B)每次求 A − B A-B A−B的所有质因子
#includebits/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;vectorLL prime;for(LL i 2;i * i tmp; i) {if(t %i 0) {prime.push_back(i);while(t%i0) 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;cinAB;LL d gcd(A,B);A A/d;B B/d;LL ans 0;get(A,B,ans);coutansendl;return 0;
}
