<p>Given a single positive integer <code>x</code>, we will write an expression of the form <code>x (op1) x (op2) x (op3) x ...</code> where each operator <code>op1</code>, <code>op2</code>, etc. is either addition, subtraction, multiplication, or division (<code>+</code>, <code>-</code>, <code>*</code>, or <code>/)</code>. For example, with <code>x = 3</code>, we might write <code>3 * 3 / 3 + 3 - 3</code> which is a value of <font face="monospace">3</font>.</p>

<p>When writing such an expression, we adhere to the following conventions:</p>

<ul>
	<li>The division operator (<code>/</code>) returns rational numbers.</li>
	<li>There are no parentheses placed anywhere.</li>
	<li>We use the usual order of operations: multiplication and division happen before addition and subtraction.</li>
	<li>It is not allowed to use the unary negation operator (<code>-</code>). For example, &quot;<code>x - x</code>&quot; is a valid expression as it only uses subtraction, but &quot;<code>-x + x</code>&quot; is not because it uses negation.</li>
</ul>

<p>We would like to write an expression with the least number of operators such that the expression equals the given <code>target</code>. Return the least number of operators used.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> x = 3, target = 19
<strong>Output:</strong> 5
<strong>Explanation:</strong> 3 * 3 + 3 * 3 + 3 / 3.
The expression contains 5 operations.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> x = 5, target = 501
<strong>Output:</strong> 8
<strong>Explanation:</strong> 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5.
The expression contains 8 operations.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> x = 100, target = 100000000
<strong>Output:</strong> 3
<strong>Explanation:</strong> 100 * 100 * 100 * 100.
The expression contains 3 operations.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= x &lt;= 100</code></li>
	<li><code>1 &lt;= target &lt;= 2 * 10<sup>8</sup></code></li>
</ul>

#define M 1000000007
#define ll long long
#define vl vector<ll>
#define MAXI 32

class Solution {

    ll multiply(ll a, ll b) {
        return ((a*b)%M +M)%M;
    }
    /*
    ll memoize(ll target, ll x, const vl& powerX, int p, map<ll,ll>& dp, bool canSubtract) {
        //cout<<target<<" -> "<<p<<endl;
        if (p == 0) {
            if (target == 0) return 0;
            int add = 2*target-1;
            int subtract = 2*(x-target);
            cout<<x<<":"<<p<<"->"<<target<<" => "<<add<<", "<<subtract<<endl;
            return min(add, subtract);
        }
        if (powerX[p] > target) return memoize(target, x, powerX, p-1, dp, true);
        if (dp.find(target) != dp.end()) return dp[target];
        dp[target] = -1;
        int quotient = target/powerX[p];
        int add = (p-1)*quotient + (quotient-1);
        int restAdd = target%powerX[p];
        int addResult = (restAdd == 0) ? add : add + memoize(restAdd, x, powerX, p-1, dp, true) + 1;
        int sub1 = p + (x-quotient)*(p-1) + (x-quotient);
        int subResult1 = (restAdd == 0) ? sub1 : sub1 + memoize(restAdd, x, powerX, p-1, dp, true) + 1;
        addResult = min(addResult, subResult1);
        if (canSubtract) {
            int subtract = memoize(powerX[p+1]-target, x, powerX, p, dp, false);
            int subResult = subtract+p+1;
            //cout<<x<<":"<<p<<" -> "<<target<<" gives "<<addResult<<", "<<subResult<<endl;
            dp[target] = min(subResult, addResult);
        } else {
            cout<<x<<":"<<p<<" -> "<<target<<" gives "<<addResult<<", "<<-1<<endl;
            dp[target] = addResult;
        }
        return dp[target];
    }

public:
    int leastOpsExpressTarget(int x, int target) {
        if (target == 1) return 1;
        vl powerX(1,1); 
        while (powerX.back()<=target) {
            ll xx = powerX.back();
            powerX.push_back(x*xx);
        }
        int n = powerX.size();
        map<ll,ll> dp;
        int tt = target;
        for (int i=n-1; i>=0; i--) {
            cout<<tt/powerX[i]<<", ";
            tt = tt%powerX[i];

        }
        cout<<endl;
        ll ans1 = memoize(target, x, powerX, n-1, dp, true);
        ll ans2 = n-1 + memoize(powerX[n-1]-target, x, powerX, n-1, dp, true);
        return min(ans1, ans2);
    }
    */

    ll memoize(ll target, ll x, const vl& powerX, int p, int maxP, map<ll,ll>& dp) {
        //cout<<"Hey, "<<target<<" "<<p<<endl;
        if (target<=0) return 0;
        if (p >= maxP) return p;    
        if (dp.find(target) != dp.end()) return dp[target];
        ll xx = (target%powerX[p+1]);
        int qa = xx/powerX[p];
        //if (qa == 0) return 0;
        ll add = (p==0) ? (2*qa-1) + 1 : (p-1)*qa + (qa-1) + 1;
        ll xxx = (powerX[p+1] - xx);
        int qs = xxx/powerX[p];
        ll sub = (p==0) ? 2*qs : (p-1)*qs + (qs-1) + 1;
        if (qa==0) add = 0;
        if (qs==0) sub = 0;
        //cout<<"--- "<<x<<":"<<p<<":"<<target<<" -> "<<xx<<" => "<<add<<endl;
        //cout<<"--- "<<x<<":"<<p<<":"<<target<<" -> "<<xxx<<" => "<<sub<<endl;
        dp[target] = add + memoize(target-xx, x, powerX, p+1, maxP, dp);
        ll subresult = (xx==0) ? INT_MAX : sub + memoize(target+xxx, x, powerX, p+1, maxP, dp);
        //cout<<"... "<<x<<":"<<p<<":"<<target<<" -> "<<xx<<" => "<<add<<endl;
        //cout<<"... "<<x<<":"<<p<<":"<<target<<" -> "<<xxx<<" => "<<sub<<endl;
        //cout<<target<<" => "<<dp[target]<<" and "<<subresult<<endl;
        dp[target] = min(dp[target], subresult);
        return dp[target];
    }

public:
    int leastOpsExpressTarget(int x, int target) {
        if (target == 1) return 1;
        vl powerX(1,1); 
        while (powerX.back()<=target) {
            ll xx = powerX.back();
            powerX.push_back(x*xx);
        }
        int n = powerX.size();
        map<ll,ll> dp;
        //int tt = target;
        //for (int i=n-1; i>=0; i--) {
            //cout<<tt/powerX[i]<<", ";
          //  tt = tt%powerX[i];

        //}
        //cout<<endl;
        ll ans = memoize(target, x, powerX, 0, n-1, dp);
        return ans-1;
    }
};
10100