The number of test cases i really large so we can't process every test individually , it will just take a lot of time. So, instead we can precalculate all the answers from 1 to 500000. here is how we should do it, it will look like a sieve of Eratostenes, we will start looping from 2 to 500000 and every time. Let us have an array A where A[I] shows the answer for I. On every step of our loop we take the current index and add it to every member of A which is divisible to I. Such as, for 2 we take 2 and add 2 to numbers , 4,6,8,10,....500000. Then we do the same for 3,4,...500000. This will not take too much time and will give us all 500000 answers we seek. Then we just need to input the queries and output the answer directly.
No comments:
Post a Comment