### hiddentesla's blog

By hiddentesla, history, 8 years ago,

the problem: http://jollybeeoj.com/problem/view/255

i tried all i can, but i can only think of preprocessing and save it in a string, then output the questions in O(1), but sadly, i cant because its memory limit exceeded, is there a math based approach?

• +5

| Write comment?
 » 8 years ago, # |   +3 Can you solve it if all squares have the same number of digits?In the general case in which squares may have a different number of digits, group them by their number of digits, and use the previous algorithm for each group.
 » 8 years ago, # |   +3 Suppose all the squares have the same number of digits. For example, let's say 2 digits.The numbers that have 2-digit squares are in the interval [4, 9].Now, given a query q, you can easily see where the digit q belongs, because there are 6 squares with 2-digits each (12 digits). 16|25|36|49|64|81Find the block (or bucket) where q falls into with a simple division.You can use this strategy in the general case, just keep track of all the intervals that contain 1-digit squares, 2-digit squares, 3-digit squares, 4-digit squares ... etc
 » 8 years ago, # |   +5 thanks for the help guys!, im guessing you have to precompute the frequency of every digit number, so thats what i did, i tried running the precomputation algo in my machine, it took about 2,5 seconds to generate, so i got worried and run it offline, then just hardcode it into the program, and got AC 1 ms :Dbut, because im curious, i just use the precomputation algo on the start of the program, and submit it again, and i got AC ~400 ms ._., so i guess my machine is just really slow :(for the future, here is how i solve the problem: https://ideone.com/S3OBbq (commented out lines is the wy i precompute)