SECUBE - Editorial

[kevinsogo]

PROBLEM LINK:

Contest
Practice

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\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:

setter
tester
editorialist

[bansal1232]

Nice editorial with good explanation!

[nabil1997]

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;
 }

[hamjosh1]

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.

[nabil1997]

@hamjosh How do you know the upper bound for t ? Your solution will get TLE.

[hamjosh1]

@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

[likecs]

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) .

[likecs]

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

[kevinsogo]

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

[likecs]

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

[kevinsogo]

@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.

[saini88]

can anyone explain why x is in the range [0,k^3) ?

[iscsi]

(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.

[tarryme123]

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.