P3397称重 | |
|
问题描述
有一台天平秤和a、b 两种砝码,每种砝码的数量无限多,要称出重量c,问最少使用多少个砝码就能办到?
输入格式
第一行,三个空格间隔的整数a,b,和c
输出格式
一行,一个整数,最少所需砝码数。数据保证,所需重量一定能称出来。
样例输入
输入样例1:
7 3 2
输入样例2:
275 110 330
输入样例3:
648 375 4002
样例输出
输出样例1:
4
输出样例2:
3
输出样例3:
123
提示
【样例说明】
样例1:使用了1 个a 砝码和3 个b 砝码
样例2:使用了0 个a 砝码和3 个b 砝码
样例3:使用了49 个a 砝码和74 个b 砝码
【数据范围】
对于60%的数据: a != b, 1<=a, b <= 100, c<= 500
对于100%的数据: a != b, 1<=a, b <= 100000, c<= 500000
来源 poj 2142