一瞬ヤバそうに見えるけど、落ち着いて考えると、 くらいまで調べればいいという
問題概要
正の整数 が与えられるので、
を満たす整数
を一つ求めよ。
制約
考えたこと
こういうの、基本的には全探索。でも という制約を見ると、
あたりまで探索しないといけないように一瞬感じてしまう。
しかし実は、そんなにいかなくても大丈夫。ここで、注目したいこととして、
という関数値が、 を 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; } } } }
おまけ: 微分
というのは、実は大体
くらいになる。これは
の微分になっている。
実際展開してみると、
となる。 が大きいときは、
に比べて、
は無視できるほど小さいので、おおむね、
〜
ということになる。
ここで、「 に比べて
は小さいので無視する」という考え方が、まさに「微分」そのものとなっている。