Create an array of Boolean elements. Size = billion.
For i:=1 to n {{ introduce a variable; element of array with index [variable] equals true }}
For i:=1 to m {{ introduce a variable; if element of array with index [variable] equals true then increase the counter }}

And finally, we output counter))
That's all), sorry for bad english

But this solution takes 58 mb of memory... ((

Edited by author 06.04.2014 16:17

Then, your code is just using a hash table method.
But I check the solution rating, someone can do it in 0.015, and many persons do it below 0.1.
How can they do that? Is because that compiler different?

It's not that hard to do it under 0.1 with C. Decent hash implementation and optimized input reading (scanf is too slow!) will actually do the 0.031 trick. 0.062 is achievable with a binary search. I achieved 0.015  by optimizing things speedwise a bit more and using as much memory as was allowed.

(studied just for fun a bit how slightly different schemes perform, have to try a few more ideas later, my current 0.015 solution is far from the optimum.)