Energy Overload

Author : knishanthreddy

Required Knowledge : Bit Manipulation

Time Complexity : $O(N\cdot log(log(N))+T\cdot log(N))$

Editorialist : knishanthreddy

Approach:

When Wanda multiplies her power by a number $K$, the same $K$ units of chaos energy are consumed. Using a single large multiplier quickly increases the cost, so the goal is to break the total required multiplication into smaller, more efficient steps.

For example, suppose Wanda needs to increase her power to $12$ from $1$. If she multiplies her current power by $12$ directly, it costs $12$ units of energy. But if she instead multiplies by $3$ and then by $2$ and then by $2$ again, the total cost becomes $3+2+2=7$ $(3\cdot 2\cdot 2 = 12)$, which is much smaller. Both approaches reach the same target power, but the second one is far more energy-efficient.

This shows that factorizing the required energy $(N/X)$ into smaller integers reduces the total energy used. In general, breaking a large multiplier into smaller factors gives a smaller or equal sum, ensuring that the total magical energy required is minimized.

We use the smallest prime factor $($SPF$)$ technique to efficiently factorize numbers. Instead of checking divisibility by every prime each time, we precompute the smallest prime factor for every number up to a limit using a modified sieve.

Then, any number can be factorized in $O(log n)$ by repeatedly dividing it by its SPF.

Setter's Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
template<class T>
void input(vector<T> &a) {
    for(auto &e:a)
        cin >> e;
}

vector<int> spf(1000006);
void sieve() {
    for(int i=1;i<=1000005;i++)
        spf[i]=i;
    for(int i=2;i*i<=1000005;i++) {
        for(int j=i*i;j<=1000005;j+=i) {
            if(spf[j]==j)
                spf[j]=i;
        }
    }
}

void solve() {       
    int n,x;
    cin >> n >> x;
    if(n%x!=0) {
        cout << -1 << endl;
        return;
    }
    int k=n/x,res=0;
    while(k>1) {
        res+=spf[k];
        k/=spf[k];
    }
    cout << res << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    cin >> t;
    sieve();
    while(t--)
        solve();
    return 0;
}

Tester's Code:

import sys
input = sys.stdin.readline

MAXN = 10**6 + 1
SPF = [0] * MAXN

def sieve():
    for i in range(2, MAXN):
        if SPF[i] != 0:
            continue
        for j in range(i, MAXN, i):
            if SPF[j] == 0:
                SPF[j] = i

def UNsolve():
    n, x = map(int, input().split())
    if n % x != 0:
        print(-1)
        return
    n //= x
    ans = 0
    while n != 1:
        ans += SPF[n]
        n //= SPF[n]
    print(ans)

def main():
    sieve()
    t = int(input())
    for _ in range(t):
        UNsolve()

if __name__ == "__main__":
    main()