Codeforces doubt

#1

question link:- https://codeforces.com/contest/1490/problem/C

attempt :- https://ide.codingblocks.com/s/435716

I’m getting TLE error. Please tell the bug, though sample input is giving correct result without error.

#2

Hey @prerak_semwal there’s no bug in your code. But the issue is with the approach. Your two loops

for(int i=2;i<=a;++i)
			{
				for(int j=1;j<=i;++j)
				{

are making time complexity of O(N^2) instead you have to tell the query in O(1) time
see the constraints
𝑥 (1≤𝑥≤10^12).
that means you are running your for loop for 10^12 for x & also for y. Too much time. Think something like we used to do it in sieve of prime numbers.

#3

@mr.encoder
I don’t know how to check O(N^2) or O(1), also I don’t know what O(N^2) means ?

Can you please explain in detail this concept ?

Also what is sieve of prime numbers ?

#4

there must be a section of time complexities in your course, you can refer that. In short O(N^2) means two nested loops starting from 0 to N . whereas O(1) means calculating or finding any thing in only one operation , like 2*3=6 calculating this is only one operation.

This is nothing but sieve of sieve of Eratosthenes it is also in your course, you can refer that too. Would suggest you to complete one topic from your course and then do it problem from other sites. This question is related to number theory. If you want it’s code i can provide you with that too.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.