1

我在“算法和数据结构”课程中遇到了这个问题

你有一个方程 x^2+s(x)+200·x=N，其中 x 和 N 是自然数，S(x) 是数字 x 的数字之和。

在输入上，我们有 N 和 A，B 使得 A≤B 和 A，B≤1,000,000,000。你需要检查在区间 [A, B] 中是否有一个自然数 x 来解方程。如果找到您需要返回该数字，否则返回 -1。

Example Input:

    1456
    10 80

Output
    
    -1

我设法通过使用一些数学和一些修改版本的蛮力算法来解决这个问题。但是有没有更有效（基于算法）的方法来解决这个问题？

这是我的代码：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Range {
    
    static int proveri(long N, long A, long B) {
        long res = 0;
        long start = (long)((-200 + Math.sqrt(4*N + 4))/2);
        //System.out.println(start);
        for (long i = Math.max(A, start); i <= B; i++) {
            res = i * i + S(i) + 200 * i;
            if(res == N)
                return (int)i;
            if(res > N)
                return -1;
        }
        
        return -1;
    }
    
    static int S(long x) {
        int sum = 0;
        while(x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
    
    public static void main(String[] args) throws Exception {
        int i,j,k;
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        long N = Long.parseLong(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        
        int res = proveri(N, A, B);
        System.out.println(res);
        
        br.close();
        
    }
    
}
4

2 回答 2

2

这是一种减少必须搜索的数字数量的方法。

考虑方程 a n x n + a n-1 x n-1 + ... + a 1 x + a 0 = 0。有理根定理指出，如果 x = p/q 是一个解，则 p 除以 a 0和 q 除以n

在您的情况下，a n为 1，a 0等于 S(x)-N。因此，我们知道任何解都必须除 S(x)-N。

这就是 ben75 的技巧所在。由于 S(x) 不能大于 81，我们可以遍历 S(x) 的所有可能值，并分别求解。像这样的东西：

for each possible value of S(x)
    loop through every factor x of S(x) - N
    check if it is between A and B, if its digits sum to S(x)
    and if it is a solution to x*x + 200x + S(x) = N.
        if it is, return it.

return -1

还有一种非常巧妙的方法可以让你遍历一个数字的所有因素，但我会让你自己解决这个问题，因为这是一门课程。我的提示是查看数字的素数分解。

于 2013-10-26T19:46:20.367 回答
0

对于方程 x^2+s(x)+200·x=N，考虑

x^2 + 200·x + (N - s(x)) = 0

对于具有整数解的 a*x^2 + b*x + c = 0 方程的解，我们需要：

b^2 - 4*a*c >= 0 and must be a perfect square

因此 200^2 - 4 * (N - s(x)) >=0 和一个正方形或

10000 >= (N - s(x)) 和 (10,000 - (N - s(x)) 必须是平方。因此平方值小于 10,000，因此您最多需要检查 100 个值。使用适当的 N 值，它可以小得多。

另请注意，由于 N < 10,000，s(x) 最多可以为 36。这些应该会大大缩小范围。

于 2013-10-26T19:49:43.670 回答