けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 166 D - I hate Factorization (茶色, 400 点)

一瞬ヤバそうに見えるけど、落ち着いて考えると、 -200 \le A, B \le 200 くらいまで調べればいいという

問題へのリンク

問題概要

正の整数  X が与えられるので、 A^{5} - B^{5} = X を満たす整数  A, B を一つ求めよ。

制約

  •  1 \le X \le 10^{9}

考えたこと

こういうの、基本的には全探索。でも  X \le 10^{9} という制約を見ると、 A, B \le 10^{9} あたりまで探索しないといけないように一瞬感じてしまう。

しかし実は、そんなにいかなくても大丈夫。ここで、注目したいこととして、

  •  y = x^{5}

という関数値が、 x を 1 増やすことによってどのくらい増加するのかを考えてみよう。これって実は微分が関係していたりするのだけど、ちょっとその知識を前提とせずに、実験してみよう。

たとえば、

  •  x = 10 のとき、 11^{5} - 10^{5} = 161051 - 100000 = 61050
  •  x = 100 のとき、 101^{5} - 100^{5} = 10510100501 - 10000000000 = 510100501

という感じだ。 x = 100 の時点で、すでに、 (x+1)^{5} - x^{5} の値が相当大きくなる。 x = 200 とかになると、

  •  201^{5} - 200^{5} = 8080401001

となって、これは  10^{9} を超えている。このことは、 A B が 200 以上になるような範囲は調べなくて良い、ということを意味している。 1 違うだけで  10^{9} も変わるのだから、 A, B が 200 以上になるような範囲で  A^{5} - B^{5} = X \le 10^{9} にするのは不可能なのだ。

解法をまとめると、

  •  -200 \le A \le 200,  -200 \le B \le 200 の範囲を全探索

すれば求めることができる。計算時間も十分間に合う。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long X;
    cin >> X;
    for (long long A = -200; A <= 200; ++A) {
        for (long long B = -200; B <= 200; ++B) {
            if (A*A*A*A*A - B*B*B*B*B == X) {
                cout << A << " " << B << endl;
                return 0;
            }
        }
    }
}

おまけ: 微分

 (x+1)^{5} - x^{5} というのは、実は大体  5x^{4} くらいになる。これは  y = x^{5}微分になっている。

実際展開してみると、

  •  (x+1)^{5} - x^{5} = 5x^{4} + 10x^{3} + 10x^{2} + 5x + 1

となる。 x が大きいときは、 x^{4} に比べて、 x^{3}, x^{2}, x, 1 は無視できるほど小さいので、おおむね、

  •  (x+1)^{5} - x^{5} 5x^{4}

ということになる。

ここで、「 x^{4} に比べて  x^{3}, x^{2}, x, 1 は小さいので無視する」という考え方が、まさに「微分」そのものとなっている。