首页 > 代码库 > HUST 1588 辗转数对
HUST 1588 辗转数对
1588 - 辗转数对
时间限制:1秒 内存限制:128兆
155 次提交 27 次通过
- 题目描述
- 假设当前有一个数对(a, b),我们可以通过一步将这个数对变为一个新数对(a + b, b)或者是(a, a + b)。
初始的数对为(1, 1),你的任务是找到一个数字k,即通过最少的步数使得这个数对中至少一个数字等于n。 - 输入
- 输入包括多组数据,每组数据包括一行,每行有一个整数n。
- 输出
- 每组数据输出一行,每行一个整数n。
- 样例输入
-
5 3
- 样例输出
-
3 2
- 提示
- 第一个样例的方法是 (1,1) ?→? (1,2) ?→? (3,2) ?→? (5,2),共3步。
- 题目链接:http://acm.hust.edu.cn/problem/show/1588
- 分析:官网给出的输出数据又是错的!正解应该如下所示,此题一直没想出怎么解,涉及到互质的问题,对于任意步骤得到的(a,b),其中a和b肯定是互质的(gcd==1)。然后想到gcd(x,y)过程中的x,y就是要保证互质一直处理下去的,那么我们此时可以O(n)枚举答案:(i,n)(当然要保证gcd(i,n)==1);再然后模拟一波减法操作。过程维护本次减法操作的总数,过程维护最小值即可。
-
1 #include <bits/stdc++.h> 2 using namespace std; 3 int gcd(int x,int y) 4 { 5 if(y==0)return x; 6 else return gcd(y,x%y); 7 } 8 int solve(int x,int y) 9 { 10 if(x==1)return y-1; 11 if(y==1) return x-1; 12 return (x-x%y)/y+solve(y,x%y); 13 } 14 int main() 15 { 16 int n,i,output; 17 while(cin>>n) 18 { 19 output=0x3f3f3f3f; 20 for(i=1;i<=n;i++) 21 { 22 if(gcd(i,n)==1) 23 output=min(solve(i,n),output); 24 } 25 cout<<output<<endl; 26 } 27 return 0; 28 }
HUST 1588 辗转数对
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。