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

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

問題へのリンク

問題概要

正の整数 が与えられるので、 を満たす整数 を一つ求めよ。

制約

• 

考えたこと

こういうの、基本的には全探索。でも という制約を見ると、 あたりまで探索しないといけないように一瞬感じてしまう。

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

• 

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

たとえば、

• のとき、
• のとき、

という感じだ。 の時点で、すでに、 の値が相当大きくなる。 とかになると、

• 

となって、これは を超えている。このことは、 や が 200 以上になるような範囲は調べなくて良い、ということを意味している。 違うだけで も変わるのだから、 が 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;
            }
        }
    }
}

おまけ: 微分

というのは、実は大体 くらいになる。これは の微分になっている。

実際展開してみると、

• 

となる。 が大きいときは、 に比べて、 は無視できるほど小さいので、おおむね、

• 〜

ということになる。

ここで、「 に比べて は小さいので無視する」という考え方が、まさに「微分」そのものとなっている。