You don't need to use Decimals. When you find all square roots of fair and square numbers, don't cache them but their squares (ie, the fair and square numbers themselves).
Then for each of the 1000 inputs, you run through the set of 46k fair and square numbers, counting how many are between A and B. no square roots required.
Yes, I could've done that, but my code from C-large-1 already use sqrt() on the bounds of the range and I never thought to change that. Since I was generating the roots instead of the full numbers it seemed natural to iterate over those. If I had thought there might be a problem with sqrt() I might've done that. However, it just never occurred to me. I just ran my C-large-2 solution against C-large-1 and got a correct answer so I assumed I hadn't made mistakes. I only found out about this after the competition was over. Oh well, this was just a qualification round anyway :)
Then for each of the 1000 inputs, you run through the set of 46k fair and square numbers, counting how many are between A and B. no square roots required.