×

# SECUBE - Editorial

Author: Istvan Nagy
Tester: Kevin Atienza
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

Easy-Medium

# PREREQUISITES:

Precomputation, modular arithmetic

# PROBLEM:

A shop is selling cubes of size $K\times K\times K$. Sebi bought one. Her sisters asked for $C$ cubes of size $1\times 1\times 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: $$-C \equiv x^3 \pmod{K^3}$$

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:

$$O(1^3 + 2^3 + 3^3 + \ldots + K^3) = O((1 + 2 + 3 + \ldots + K)^2) = O((K^2)^2) = O(K^4)$$

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: $$a^{\phi(n)/d} \equiv 1 \pmod{n}$$ 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

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

1.7k586142
accept rate: 11%

19.8k350498541

2

@kevinsogo, shouldn't the complexity for Hansel lemma part be $O(K + {\log}^{2}K)$

(21 Nov '16, 04:53) 6★

@likecs It seems you're right. I updated it.

(21 Nov '16, 05:19)

@kevinsogo , can we extend to idea to general existence of ${e}^{th}$ root of number in any finite field?

(21 Nov '16, 05:47) 6★

@likecs Yes, because the multiplicative group of any finite field has a generator, which is all that's required for this theorem: The criterion $n = 2, 4, p^k$ or $2p^k$ precisely says that the multiplicative group mod $n$ has a generator. The theorem is in fact easy to prove given a generator: consider the powers of the generator and what it means to be a power and a root in the field. Although, you need to replace $\phi(p^k)$ with $p^k - 1$, because the field with size $p^k$ has $p^k - 1$ invertible elements.

(21 Nov '16, 05:56)

 6 Nice problem. Here is my solution as per the Hensel's lemma. Complexity : $O(K + {\log}^2k)$ $K$ for linear sieve of Eratosthenes. ${\log}^2k$ for factorisation of $n$ in input and for each each calculating ${a}^{\phi(p^k) / d}$ (mod $p^k$) . answered 21 Nov '16, 04:52 6★likecs 3.7k●24●81 accept rate: 9%
 4 Nice editorial with good explanation! answered 21 Nov '16, 00:21 2.8k●1●4●19 accept rate: 16%
 0 I had the following solution for this problem. But it was wrong. Can someone explain to me why my solution is not correct? My approach: $(k^3 - C) + t*k^3 = x^3$ Now, $a=(k^3 - C)$ and $b=k^3$ so, I want to find out if, $a+t*b=x^3$ Now, lets assume, $a=dv1*dv2$ so, if I can write $a+t*b=x^3$ in the form, $dv1*(dv2 + q)$ where, $dv2+q=dv1^2$ then, this must be a cube else not. I do the same for div2. Here is my code. int main() { int tc; sfi(tc); while(tc--) { int k,c; sfii(k,c); ll a = (k*k*k)-c; ll b = (k*k*k); ll sq = sqrt(a)+1; int ans=0; if(a==0 || c==0) ans=1; for(ll dv1 = 1 ; dv1 < = sq; dv1++) { ll dv2; if(a%dv1==0) { dv2=a/dv1; ll sqrr = dv1*dv1; if((sqrr-dv2) > 0 && ((sqrr-dv2) * dv1 % b) == 0) { ans=1; } sqrr = dv2*dv2; if((sqrr-dv1) > 0 && ((sqrr-dv1) * dv2 ) % b == 0) { ans=1; } } } if(ans) pf("YES\n"); else pf("NO\n"); } return 0; } link This answer is marked "community wiki". answered 21 Nov '16, 00:33 11●11●17●16 accept rate: 0%
 0 I want to know why would this solution fail link . Where we would simply be using (K3−C)+tK3=x3 and checking for all t if that satisfies this solution. answered 21 Nov '16, 00:36 1★hamjosh1 1●1 accept rate: 0% @nabil1997 it wasn't giving tle but wa in the while loop it was testing if the result exceed 100X100X100 as that was the limit it was breaking out of the loop (21 Nov '16, 00:56) hamjosh11★
 0 @hamjosh How do you know the upper bound for $t$ ? Your solution will get TLE. answered 21 Nov '16, 00:52 11●11●17●16 accept rate: 0%
 0 can anyone explain why x is in the range [0,k^3) ? answered 22 Nov '16, 12:59 3★saini88 1 accept rate: 0% (x+(tk^3))^3 = x^3 + 3x^2tk^3+3xt^2k^6+t^3k^9 = x^3 mod (k^3), beause all of divisible with k^3 except x^3 so it is enough to consieder [0,k^3) range. (22 Nov '16, 14:38) iscsi6★
 -1 Law, except in cases of force majeure, to receive an amount predetermined by the postal operator in case of loss, theft, destruction or deterioration of certified shipments, and treated usps shipments with declared value right to receive a proportional amount to the declared by the sender. answered 20 Jan '17, 01:37 -7 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,723
×145
×129
×60
×15

question asked: 20 Nov '16, 21:43

question was seen: 2,932 times

last updated: 20 Jan '17, 01:37