对于一个数字对(a, b)，我们可以通过一次操作将其变为新数字对(a+b, b)或(a, a+b)。
给定一正整数n，问最少需要多少次操作可将数字对(1, 1)变为一个数字对，该数字对至少有一个数字为n。
直接爆搜会TLE
突然发现这个过程跟辗转相除法类似，
那么对于$(a,b)$->$(1,1)$
如果还原的过程$a==b==1$还原成功，反之失败
加速这个过程的方法$(a,b)$->$(b$,$a$%$b)$需要的步数是$a/b$
#include<bits/stdc++.h> #define inf 0x7fffffff #define LL long long using namespace std; LL n,ans; 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() { scanf("%lld",&n); ans=inf; for(LL i=1;i<=n;i++) ans=min(ans,calc(n,i)); printf("%lld",ans); return 0; }
原文：https://www.cnblogs.com/song-/p/9716712.html