【競プロ精進ログ】【2021/03/05】ABC166: D

競技プログラミングのための精進履歴をブログ形式で残していきます。

目標は AtCoder 水色！
今のレートは茶色です。

本日の精進ツリーは以下のとおり。

精進ツリー

ABC166: D – I hate Factorization
まとめ

ABC166: D – I hate Factorization

ABC166 より、 ABC166: D – I hate Factorizationを解きました。
難易度は茶色。

これ系は全探索かな？と思いつつ、負の数を入れたときの計算量の多さにあきらめてました。

しかしちゃんと確認してみると、 5乗の制約のおかげで実際の計算量自体はそんなに多くない感じでしたので、全探索で AC。

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;

#define MAX 100010
#define NIL -1

using lint = long long int;
using P = pair<lint, lint>;

/*************************************************************************************
NOTE: 

・方程式を移項すると、 A^5 = X + B^5 を満たす
・5乗なので、A^5 もしくは B^5 は負の数になりうる
・左辺の因数分解してみたけどあんまり意味なさそう
・全探索したいけど、負の数も含めると厳しそう

↓
・と思ったが、5乗という制約を考えると、 -200 <= A,B <= 200 程度の範囲の全探索でよさそう
*************************************************************************************/

/*************************************************************************************
LOGIC: 
1. AとBのそれぞれを、-200 <= A,B <= 200 の範囲で全探索する
*************************************************************************************/

int main()
{
    lint X;
    cin >> X;

    rep(i, 201)
    {
        lint pos_a = i;
        lint neg_a = (-1) * i;
        
        rep(j, 201)
        {
            lint pos_b = j;
            lint neg_b = (-1) * j;

            if (pow(pos_a, 5) == X + pow(pos_b, 5))
            {
                cout << pos_a << " " << pos_b << endl; 
                return 0;
            }
            if (pow(pos_a, 5) == X + pow(neg_b, 5))
            {
                cout << pos_a << " " << neg_b << endl;
                return 0;
            } 
            if (pow(neg_a, 5) == X + pow(pos_b, 5))
            {
                cout << neg_a << " " << pos_b << endl;
                return 0;
            }
            if (pow(neg_a, 5) == X + pow(pos_b, 5))
            {
                cout << neg_a << " " << neg_b << endl;
                return 0;
            }
        }
    }
    return 0;
}