P2090 数字对

题目描述

对于一个数字对(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==) return a-;

    if(!b) return inf;

    return a/b+calc(b,a%b);

}

int main()

{

    scanf("%lld",&n);

    ans=inf;

    for(LL i=;i<=n;i++)

        ans=min(ans,calc(n,i));

    printf("%lld",ans);

    return ;

}

巴特西

洛谷——P2090 数字对

P2090 数字对

题目描述

最新文章

热门文章