1011: 木木的电阻

时间限制: C/C++ 1 s      Java/Python 3 s      内存限制: 128 MB      答案正确: 32 / 278     

题目描述

这是最欢乐一年,这是最悲剧的一年。
悲剧的那些事情,悲剧的那些人啊。
你们都要离我远去了。
---- 魔法第三章
其实上面这一段话来自于木木编写的超级程序,是一段魔法咒语,是通过暴力搜索找到的这么一段话。
当木木念完这句话的时候,发现来到了一个新的地方,这个地方有很多和人类长得不同的生物在活动,看上去应该是外星人,而且从这个地方的新名字也可以知道这些。这地方已经被称作——蓝海星。
木木有一天有幸来到宇航局面试,然而宇航局出了一个难题,只给木木一大堆1$\Omega$的电阻,要木木用串联和并联的方式做出给定阻值的电阻。而且要求用尽量少的电阻。

输入

输入数据会有多组数据。每组数据占一行。
每行有两个数字a和b,表示需要构造出阻值为$\frac{a}{b} \Omega $的电阻。
这里a,b有$$1<=a,b<=10^{18} $$
当a,b都等于0,输入结束,并且这组数据不需要处理。

输出

对于每一组数据,输出只占一行。
每行输出一个数字min,表示最少需要多少个1$\Omega$的电阻可以组合出阻值为$\frac{a}{b}\Omega$的电阻。

样例输入

1 2
2 1
0 0

样例输出

2
2

提示

来源

标签

#校赛  

提交代码






© 2019 JustOJ     中文  English  | l.jiang.1024@gmail.com | Docs | System Info | Telegram Group | Telegram Channel