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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python

面向对象的三大特性(封装、继承、多态)

继承 什么是继承 继承是一种创建新类的方式,在python中,新建的类可以继承一个或多个父类,父类又可称为基类或超类,新建的类称为派生类或子类 python中类...

1.4K9
来自专栏阿凯的Excel

筛选功能(Pandas读书笔记9)

今天和大家分享如果使用Pandas实现单、多条件筛选、模糊筛选。 还是老套路,我们需要先读取一组数据作为测试文件。 测试文件使用读书笔记7的材料,传送门如下: ...

1K6
来自专栏java一日一条

成为优秀Swift开发者的10条建议

在这里给大家分享一些帮助大家成为更优秀的Swift开发者的建议,让你的代码,写的更少,性能更优 。

1072
来自专栏java达人

哈希表

哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接...

1797
来自专栏灯塔大数据

每周学点大数据 | No.9递归——以阶乘为例

No.9期 递归——以阶乘为例 Mr. 王:我们介绍一个在计算机算法设计和程序设计中都非常常见的概念——递归。 小可:什么是递归呢? Mr. 王:从程序设计的...

3444
来自专栏阿凯的Excel

文本数字拆分技巧

Excel处理人员呢,最喜欢的就是规范化的表,那什么样子的表是规范的呢?给大家个图片感受一下! ? 今天的要和大家分享的就是和规范化图表格格不入的,需要由不规...

3236
来自专栏take time, save time

你所能用到的BMP格式介绍(二)

一、可能你忽视的基础         在正式开始之前,我不得不从最基本的地方开始,因为这些地方大多数人会忽视的一干二净,如果不在开始进行说明,那么在后面一定会有...

2907
来自专栏阿凯的Excel

让你眼花缭乱的匹配函数反查技巧

小编已经连续写了三期关于匹配函数的用法,匹配函数的扛把子(老大)肯定是Vlookup函数莫属,但是Vlookup函数有一个问题,就是要查找的内容,必须在查找内容...

2926
来自专栏Crossin的编程教室

【每周一坑】罗马数字转换

罗马数字是欧洲在阿拉伯数字传入之前使用的一种数码,现在的使用已经非常少了,大概偶尔会在钟表、文章中的标号等地方还能见到。 罗马数字采用七个罗马字母作数字、即 I...

3307
来自专栏C/C++基础

统计无符号整数二进制中1的个数(Hamming weight)

之所以来记录这个问题的解法,是因为在在线编程中经常遇到,比如编程之美和京东的校招笔试以及很多其他公司都累此不疲的出这个考题。看似简单的问题,背后却隐藏着很多精妙...

1382

扫码关注云+社区