[原创]HUST 1588 辗转数对 []【数学】

2017-02-10 16:24:08 Tabris_ 阅读数：184

博客爬取于2020-06-14 22:41:43
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54971709

题目链接：https://vjudge.net/problem/HUST-1588
--------------------------------------------------------------------------------------------------------.
1588 - 辗转数对

时间限制：1秒 内存限制：128兆
139 次提交 23 次通过
题目描述
假设当前有一个数对(a, b)，我们可以通过一步将这个数对变为一个新数对(a + b, b)或者是(a, a + b)。
初始的数对为(1, 1)，你的任务是找到一个数字k，即通过最少的步数使得这个数对中至少一个数字等于n。
输入
输入包括多组数据，每组数据包括一行，每行有一个整数n。
输出
每组数据输出一行，每行一个整数n。
样例输入
5
3
样例输出
3
0
提示
第一个样例的方法是 (1,1) → (1,2) → (3,2) → (5,2)，共3步。
来源
--------------------------------------------------------------------------------------------------------.
解题思路:

这个题不难发现，对于我们累加出来的（a，b）一定是互质的
然后想到Gcd（x，y）过程中的x，y就是要保证互质一直处理下去的
那么其实就是在问gcd过程中x%y要减多少次
那么接下来我们枚举终点（i，n）维护最小值即可

附本题代码
--------------------------------------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int ans;

bool gett(int a,int b){
    if(gcd(a,b)!=1) return false;
    int res = 1;
    while(a!=1||b!=1){
        if(a>b) a=a-b;
        else    b=b-a;
        res++;
    }
    ans = min(ans,res);
    return true;
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        ans = INF;
        if(n==1) {puts("0");continue; }
        if(n==2) {puts("1");continue; }
        for(int i=1;i<=n;i++)       get(i,n-i);
        printf("%d\n",ans);
    }
    return 0;
}