题解 P2090 【数字对】

Tyw_ei · 2017-09-19 16:00:24 · 题解

如果这个题你选择正着推的话,那么除了dfs就没有什么后续了

那么考虑从答案入手:

1.最后的答案一定满足(n,i)(i<=n);

2.从这一状态到以前的状态,可以很好的表示,(maxn-mini,mini)-->(mini,maxn)

一定是大的减去小的;

3.如果maxn是mini的倍数,则要通过取模来加速;

4.由三可知一个新的问题就是如何判断他们最后是从(1,1)转移过来?

答案是两个数必须互质;如果他们有相同的因子,最后减出来的一定是这个因子的倍数或0;

5.与gcd的联系:因为辗转相减就是求gcd的手段,当一个数为0的时候,另一个数就是原数对的最大公约数

而题目又在他们互质的时候才能转移,显然a==1的时候才可以

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#define INF 2147483647
using namespace std;

int ans=INF,n;

void check(int a,int b,int step){
    if(b==0){
        if(a==1)ans=min(ans,step);
        return;
    }
    if(a<b)swap(a,b);
    check(b,a%b,step+a/b);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
        check(n,i,0);
    printf("%d",ans-1);
    return 0;
}