题解 P2090 【数字对】

· · 题解

给一个数字对(a,b)，考虑如何把它还原成(1,1)

我们想：

若a>b那么(a,b)->(a-b,b);

若b>a那么(a,b)->(a,b-a);

若a==b

若(a==b==1)那么我们就还原成功了！

否则,(a,b)->(a,0)/(0,b),无法还原到(1,1),不满足条件。

如何加速这个过程呢？

我们感觉这个东西和gcd（辗转相除法）很像

若a>b,则(a,b)->(a mod b,b),步数+a/b;

若b>a,同理可得。

对于给定的n，枚举所有的i，还原(n,i),取最小步数为解

时间复杂度O(n*logn)

所以，CODE:

#include<bits/stdc++.h>
#define LL long long
#define NAME "numpair"
#define setfile() freopen(NAME".in","r",stdin),freopen(NAME".out","w",stdout)
#define closefile() fclose(stdin),fclose(stdout)
LL inf=1e9,n,ans=1e9;
using namespace std;
LL calc(LL a,LL b){
    if (b==1) return a-1;
    if (!b) return inf;
    return a/b+calc(b,a%b);
}
int main(){
    setfile();
    scanf("%lld",&n);
    for (int i=1;i<n;i++)
        ans=min(ans,calc(n,i));
    printf("%lld\n",ans);
    closefile();
    return 0;
}