Any TLE experts here?

i am still unable to find tle in this code…could anyone spare some time to give me suggestions?thanking you in advance!
#include<stdio.h>
void main()
{
int t;
scanf("%d",&t);
while(t–)
{
int n,cc,mc,j;
scanf("%d %d %d %d",&n,&j,&cc,&mc);
int b[2*n],i,flag=0;
for(i=0;i<n;i++)
{ b[i]=b[n+i]=i; }
for(i=cc;i<(cc+n);i+=j)
{
if(b[i]==mc)
{ flag=1;
break;}
}
if(flag==1)
printf(“YES\n”);
else
printf(“NO\n”);
}
}

link for the problem is https://www.codechef.com/problems/CVDRUN

You need to find whether

(X+K)%N equals to Y

Let’s say you added K to X a times. So, you have the value X+aK. You need to check whether this expression gives a remainder Y when divided by N. In other words, we need to check whether

X+aK = Y+bN

Rearranging, we get

X-Y= bN-aK

Adjusting the constants, we get

X-Y= b’N+a’K

Above equation is a linear Diophantine equation which has an integral solution iff X-Y is divisible by gcd(N,K).

So, to solve the problem, all you need to do now is to check whether abs(X-Y)%gcd(N,K) is 0. If it’s 0, then YES, else NO.

You can use this one to reduce time complexity to O(lg n)

1 Like

In second for loop :
for(i=cc; i<(cc+n);i+=j)

When j is 0, it will run infinitely giving tle.

3 Likes

sure…thanks alot
going to try…if failed,will ask u for one more time.

i see… :)thanks for this one!!!