找到转换为基数 10 时相等的两个基数

Question

今天我遇到了一个非常具有挑战性的问题。想不出办法解决。

给定 6 个数字作为输入：a1、a2、a3、b1、b2、b3，找到 2 个数字 X 和 Y，满足 a1 * x^2 + a2 ^ x + a3 = b1 * y^2 + b2 * y + b3。 X 和 Y 必须介于 10 和 15000 之间（含）。

我尝试过的：

我已经尝试了 10-15000 的所有 X 值和 10-15000 的所有 Y 值，并检查它们是否满足等式。但是，这种方法非常慢。有人有更快的解决方案吗？谢谢

我的错误代码：

for (int i = 0; i < k; i++) {
    int a, b;
    cin >> a >> b;
    for (int i = 10; i <= 15000; i++) {
        for (int j = 10; j <= 15000; j++) {
            if (conv(a, i) == conv(b, j)) {
                cout << i << " " << j << endl;
                j = 20000;
                i = 20000;
            }
        }
    }
}
long long conv(int x, int b) {
long long ans = 0;
int count = 0;
while (x) {
    int y = x % 10;
    ans += y * poww(b, count);
    count++;
    x /= 10;
}
return ans;
}
long long poww(int x, int y) {
long long ans = 1;
while (y != 0) {
    ans *= x;
    y--;
}
return ans;
}

Answer 1

我认为这可能是练习编写一些 Java 代码的好机会，并提出了以下解决方案。在我的系统上，它在 1 毫秒内给出了两个数字 419 和 792 的解决方案（正如您在之前对问题的编辑中所写，结果应该是 Base X: 47 Base Y: 35）。

代码只是使用了一些智能暴力:)。

See it running online.

public class TwoBases {
    public static void main(String[] args) {
        long beg = System.nanoTime();
        solve(419, 792);
        System.out.println("Time needed to calculate: "+(System.nanoTime()-beg)/1000000.0 + "ms");
    }

    public static void solve(int a, int b) {
        int[] aDigits = new int[3];
        int[] bDigits = new int[3];
        for (int i = 0; i < 3; i++) {
            aDigits[2 - i] = (a / (int) Math.pow(10, i)) % 10;
            bDigits[2 - i] = (b / (int) Math.pow(10, i)) % 10;
        }
        for (int x = 10; x <= 15000; x++) {
            int numBaseX = digitsToBase10(aDigits, x);
            int y = 10;
            while (y <= 15000) {
                int numBaseY = digitsToBase10(bDigits, y);
                if (numBaseX == numBaseY) {
                    System.out.println("Base X: " + x + " Base Y: " + y);
                    return;
                } else if (numBaseY > numBaseX) {
                    break;
                } else {
                    y++;
                }
            }
        }
        System.out.println("Nothing found");
    }

    public static int digitsToBase10(int[] digits, int b) {
        int res = 0;
        for (int i = 0; i < digits.length; i++) {
            res += digits[i] * (int) Math.pow(b, digits.length - 1 - i);
        }
        return res;
    }
}

找到转换为基数 10 时相等的两个基数

Finding Two Bases Which When Converted to Base 10 Are Equal

c++

java

math

numbers

digit