找出将 a/b 转换为 c/d 的步数，使得 0<a<b<100000 和 0<c<d<100000，如果没有办法，则 none

Question

Original problem. Given two valid fractions a/b and c/d. Each transformation is adding 1 to a and b, then optimizing a/b. Find the number of steps transforming a/b into c/d so that 0<a<b<100000 and 0<c<d<100000, or none if there is no ways.

#include <iostream>
#include <math.h>
using namespace std;
int gcd(int x, int y) {
    while(y) {
        int r=x%y;
        x=y;
        y=r;
    }
    return x;
}
int main() {
    int a, b, c, d;
    cin>>a>>b>>c>>d;
    int i=0;
    while (b<d) {
        if (a*d<b*c) {
            a++;
            b++;
            a/=gcd(a, b);
            b/=gcd(a, b);
            i++;
        }
        else if (a*d==b*c) {
            cout<<i;
            break;
        }
        else {
            cout<<0;
            break;
        }
    }
}

有些错误，即输入

答案是5，但不是这里的输出。我需要帮助，感谢您的所有好评！

Answer 1

第一个问题是while (b<d)。在您的示例中 6<3 是错误的，因此 while 循环被完全跳过。

下一个问题是

a/=gcd(a, b);
b/=gcd(a, b);

您正在更改 a 并为 a 和 b 计算两个不同的 gcd。

您可以使用

修复它

const auto g = gcd(a, b);
a/=g;
b/=g;

找出将 a/b 转换为 c/d 的步数，使得 0<a<b<100000 和 0<c<d<100000，如果没有办法，则 none

Find the number of steps transforming a/b into c/d so that 0<a<b<100000 and 0<c<d<100000, or none if there is no ways

c++

equation

if-statement

while-loop

fractions