1

「アルゴリズムとデータ構造」コースでこの問題があります

式 x^2+s(x)+200·x=N があります。ここで、x と N は自然数で、S(x) は数値 x の桁数の合計です。

入力には、A≤B および A, B≤1,000,000,000 となる N および A, B があります。方程式を解く区間 [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を割ります

あなたの場合、nは 1 で、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)) は正方形でなければなりません。したがって、2 乗の値は 10,000 未満であり、チェックする必要がある値は最大で 100 個です。 N の適切な値を使用すると、はるかに小さくすることができます。

また、N < 10,000 であるため、s(x) は最大で 36 になる可能性があることに注意してください。これらにより、範囲がかなり縮小されます。

于 2013-10-26T19:49:43.670 に答える