### PROBLEM LINK:

**Author:** Istvan Nagy

**Tester:** Kevin Atienza

**Translators:** Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)

**Editorialist:** Kevin Atienza

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Precomputation, modular arithmetic

### PROBLEM:

A shop is selling cubes of size K imes K imes K. Sebi bought one. Her sisters asked for C cubes of size 1 imes 1 imes 1. Is it possible for Sebi to buy some number of cubes so that he can build another cube (of possibly a different size) out of those and the remaining cubes he has?

### QUICK EXPLANATION:

The answer is `YES`

iff there is some x such that x^3 + C \equiv 0 \pmod{K^3}. Thus, we want to know if -C is a *perfect cube mod K^3*. We only need to try x up to K^3.

To speed this up, notice that K \le 100, which means we can precompute all cubes modulo K^3 quickly, for all K, before processing any input.

### EXPLANATION:

Let’s keep track of what’s happening. Initially, Sebi has K^3 individual cubes. After her sister takes some cubes, he has exactly K^3 - C left. Now he wants to buy some more K^3-sized cubes, say t more, such that he can form another cube out of those cubes and the K^3 - C leftovers he has. In other words, (K^3 - C) + tK^3 must be equal to x^3 for some integer x > 0, i.e. (K^3 - C) + tK^3 = x^3. Thus, the question now becomes: *are there some integers t, x > 0 satisfying (K^3 - C) + tK^3 = x^3*?

By *reducing this equation modulo K^3*, we get the following:

This says that (-C) must be a **perfect cube modulo K^3**. Any solution must satisfy this, so we now have one *necessary* criterion for the existence of the solution (x,t). But is this enough?

Fortunately yes! If -C is a perfect cube modulo K^3, i.e. if a^3 \equiv -C \pmod{K^3}, then by definition, a^3 = -C + bK^3 for some integer b. This gives us the solution (x,t) = (a,b-1)! Note that if x or t are not positive, then we can simply increase x by K^3 arbitrarily until they both become positive.

Thus, the remaining part is how to determine if a number is a perfect cube modulo K^3. To answer this, we notice the constraint K \le 100. This means that even though there are many test cases, there can only be a few distinct $K$s, and for each K, we can simply *precompute* the perfect cubes modulo K^3! To do so, notice that we only need to consider x^3 for x in the range [0,K^3), because x^3 and (x \pm c\cdot K)^3 are the same modulo K^3!

So how fast does this run? The precomputation part runs in:

After that, each test case can be answered in O(1) with just a simple lookup!

*Fun fact*: We note that there exist faster solutions for this problem. For example, there exists a solution which runs in O(K \log \log K) time precomputation and O(\log^2 K) time per query. It uses the Chinese remainder theorem, Hensel’s lifting lemma, and the following theorem about existence of powers modulo primes:

*If n is the form 2, 4, p^k or 2p^k for k \ge 1 and some odd prime p, and if \gcd(a,n) = 1, then at least one solution to x^t \equiv a \pmod{n} exists iff:*

*where \phi is Euler’s totient function and d = \gcd(t,\phi(n)). If there is at least one solution, then there are exactly d solutions.*

We leave this algorithm for the reader to discover.

During the round however, it might actually cost you more time pursuing this fast solution instead of the simpler solution above, so this is a lesson to not overthink things

### Time Complexity:

Either

- O(K_{\max}^4) preprocessing, O(1) query
- O(K_{\max} \log \log K_{\max}) preprocessing, O(\log^2 K) query