算法思路 先用辗转相除法求a与b的最大公约数,将a与b的比例化至最简, 然后在A->a与B->b中选择缩小的倍数最小的,该倍数乘以a和b即为答案 时间复杂度分析 该算法的时间复杂度为欧几里得算法的时间复杂度,为O(lg min(a,b)),是对数级别的 实现代码 #include <iostream> using namespace std; /** * 牛客 比例问题 * 运行时间 4ms 占用内存432KB * */ int get_greatest_common_divisor(int a,int b){ if(a<b) swap(a,b); do{...