codeforces343A A. Rational Resistance
standard output
Mad scientist Mike is building a time machine in his spare time. To finish the work, he needs a resistor with a certain resistance value.
However, all Mike has is lots of identical resistors with unit resistance
R0 = 1. Elements with other resistance can be constructed from these resistors. In this problem, we will consider the following as elements:
- one resistor;
- an element and one resistor plugged in sequence;
- an element and one resistor plugged in parallel.
With the consecutive connection the resistance of the new element equals
R = Re + R0. With the parallel connection the resistance of the new element equals.
In this caseRe equals the resistance of the element being connected.
Mike needs to assemble an element with a resistance equal to the fraction . Determine the smallest possible number of resistors
he needs to make such an element.
The single input line contains two space-separated integers
a and b (1 ≤ a, b ≤ 1018). It is guaranteed that the fraction
is irreducible. It is guaranteed that a solution always exists.
Print a single number — the answer to the problem.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use thecin,
cout streams or the%I64d specifier.
1 1
1
3 2
3
199 200
200
In the first sample, one resistor is enough.
In the second sample one can connect the resistors in parallel, take the resulting element and connect it to a third resistor consecutively. Then, we get an element with resistance.
We cannot make this element using two resistors.
题目意思:有很多1欧姆的电阻,问最少用多少个电阻可以等效成a/b欧姆;
注意用__int64;
分析:这个题有个规律,就是a/b,b/a所需要的电阻一样,只是串并联关系不一样而已,因此该题可以这样考虑:写成假分子的形式a/b,(a>b)取整数部分,然后对剩余的电阻a1/b1进行类似的运算(a1>b1)
知道a/b可以除尽位置sum记录的整数值之和就是答案:
程序:
#include"string.h"
#include"stdio.h"
int main()
{
__int64 a,b,p,t;
while(scanf("%I64d%I64d",&a,&b)!=-1)
{
__int64 sum=0;
while(1)
{
if(a<b)
{
t=a;
a=b;
b=t;
}
p=a/b;
sum+=p;
if(a%b==0)
break;
a-=b*p;
}
printf("%I64d\n",sum);
}
}
最新文章
- javascript中的Array对象 —— 数组的合并、转换、迭代、排序、堆栈
- hbase集群安装与部署
- ORACLE 利用 REPLACE函数替换字段字符串
- jQuery源码 Ajax模块分析
- HTML中<;meta>;标签如何正确使用
- 关于python 序列 深拷贝
- 同步git修改文件到远端服务器脚本
- linux下xampp集成包安装配置方法
- Windows平台下的session0创建进程的问题与解决办法
- Delphi中一些DLL的运用(要传递Application和Screen,似乎还忘了传递提示控件)
- 集合:在我的世界里,你就是唯一 - 零基础入门学习Python027
- 读书笔记 effective c++ Item 12 拷贝对象的所有部分
- VMware虚拟机上建立HTTP服务步骤
- 我对AOP的理解
- 题 FatMouse‘Trade
- 使用 Node.js 搭建API 网关
- oracle中常见的查询操作
- Elasticsearch查询Index以及删除
- node.js下载安装
- 如何同步两台Linux机器的时间?