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