ARC159B GCD Subtraction

本文主要是介绍ARC159B GCD Subtraction，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

---

这里有一个性质，对于互质的两个数 $a,b$，它们的答案与 $ag,bg$ 两数的答案相等。设 $ag,bg$ 第 $i$ 操作减去的数 $x$；$a,b$ 第 $i$ 次操作减去的数为 $y$，显然有 $x=gy$，前者减去的数是后者的 $g$ 倍，而 $ag,bg$ 又恰好是 $a,b$ 的 $g$ 倍，得证。

所以我们可以先把 $a,b$ 除以其最大公约数，变成互质的 $a,b$。此时最大公约数是 $1$，如果后面的最大公约数一直是 $1$，直接模拟必然超时。

对于特殊情况：如果 $a=b$，步数为 $1$；如果 $a,b$ 有一者为 $1$，步数为 $1$；如果 $|a-b|=1$，步数为 $\min (a,b)$。

考虑一般情况：快速求出最小的 $k$，存在大于 $1$ 的数 $p$ 满足 $\gcd (a-k,b-k)=p$。显然限定 $p$ 为质数不会增大 $k$。枚举 $10^6$ 以内的质数求出最小的 $k$（注意 $k<\min (a,b)$ 等细节），然后重复上面的流程即可。

分析时间复杂度：设 $N=\max (A,B)$求最小的 $k$ 是 $O(\frac{\sqrt{N}}{\ln N})$ 的，每次 $a,b$ 都要除以最大公约数，因此会有 $O({\log }_{2}N)$ 次流程，预处理质数 $O(\sqrt{N})$，总的时间复杂度为 $O(\sqrt{N})$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+1;
ll n,m,ans;
int a[N],p[N],cnt;
ll gcd(ll a,ll b)
{return !b?a:gcd(b,a%b);
}
int main()
{a[1]=1;for(int i=2;i<N;i++){if(!a[i]) p[++cnt]=i;for(int j=1;j<=cnt&&i*p[j]<N;j++){a[i*p[j]]=1;if(i%p[j]==0) break;}}cin>>n>>m;while(n&&m){if(n>m) swap(n,m);ll g=gcd(n,m);n/=g,m/=g;if(abs(n-m)<=1) cout<<ans+min(n,m),exit(0);ll k=1e12,P=0;for(int i=1;i<=cnt&&p[i]<=n;i++) if(p[i]<=n&&n%p[i]==m%p[i]) k=min(k,n%p[i]);if(k==1e12){ll x=abs(n-m);if(x<=n&&n%x==m%x) k=n%x;else k=n;}ans+=k;n-=k,m-=k;}cout<<ans;
}

这篇关于ARC159B GCD Subtraction的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---