This problem is very simple stated. You are given a positive integer **X** and you want to compute its square. The good thing is that **X** consists only of **N** repetitions of the same digit. Sounds very simple, but the problem is that **X** can be very large here. In all subtasts, you have to handle at most $20$ test cases. In order to return the result, you are asked to compute its hash with the given hash function. Since this can be done in linear time in terms of the length of the result, from now, we assume that you only need to compute the result as $X \cdot X$.
Since squaring a number is multiplying it by itself, use [long multiplication], which is sometimes called grade-school multiplication or Standard Algorithm, and speed up the computation using prefix and suffix sums of digits of the intermediate result.
In the simplest subtask, since **N** is at most $9$, we know that **X** fits in $32$-bit integer and hence, the result fits in $64$-bit integer, so you can compute it as the product of two $32$ bit integers.
In the second subtask, **N** is at most $100$, so the previous method cannot be used here. The good news, that **N** is not as big to prevent us from using standard, taught in elementary school, [long multiplication]. Using this method, we can easily compute the result for a single test case in $O(N^2)$ time.
In this subtask, we have $N$ up to $2 \cdot 10^4$, and you can solve this task using any reasonable speed up of a quadratic multiplication algorithm, so in other words, you can solve the multiplication of two long number problem in general. This can be done, probably in the easiest way, by representing $X$ in some significantly larger base than $10$ and then applying the standard long multiplication algorithm. Other, well-known methods, for multiplying fast two long numbers are FFT and Karatsuba algorithm, but since they are not so easy to implement, they are not so good choices here.
In the last subtask, you have to deal with a really big number, consisting of up to $10^6$ digits, and any of above methods will not work here. In order to solve this problem, we will strongly use the fact that $X$ consists of the same digit repeated many times. Let's take a closer look at the long multiplication algorithm:
d d ... d d d = X * d d ... d d d = X ------------- m[k] m[k-1] ... m m m m[k] m[k-1] ... m m m m[k] m[k-1] ... m m m . . . m[k] m[k-1] ... m m m</sub> m[k] m[k-1] ... m m m</sub>
Let $M = d \cdot X$ and $m[k], m[k-1], \ldots, m$ be the digits of $M$. First important thing to notice, is that $M$ can have $N$ or $N + 1$ digits. Now, in order to get the result, we need to compute the following sum: $M + 10 \cdot M + 10^2 \cdot M + \ldots$. We can do this by accumulating the sum of each column from above schema independently. Notice that, the exact digits we need to accumulate in a certain column, depends only on the number of digits of $M$.
After that, in order to get the final result, we have to normalize the results from each column to base 10. This is easy to do by iterating over sums of columns from right to left, and computing for each one its sum modulo 10 as the digit corresponding to this column in the result, and carrying the outcome of dividing this sum by 10 the the next column.
However, if we accumulate the sum of each column naively, the method has quadratic time complexity, which is too much for this subtask. In order to speed it up, let’s take a closer look at the above adding schema. The result for each column is the sum of the first l digits of M for some l or the sum of the last l digits of M for some l. So in order to get the sum of each column, we can first precompute prefix sums and suffix sums of digits of M and then we can get the sum for each column in constant time, which is a big speed up over summing these digits naively.
This method has linear time complexity, but be aware of the your implementation, especially avoid copying and reversing arrays. In addition, it is better to implement the solution using static array rather than dynamic ones.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found [here].
Tester’s solution can be found [here].
: http://www.codechef.com/problems/FSTSQ : http://www.codechef.com/LTIME29/problems/FSTSQ : http://www.codechef.com/download/Solutions/LTIME28/Setter/FSTSQ.cpp : http://www.codechef.com/download/Solutions/LTIME28/Tester/FSTSQ.cpp