segment tree is not required.Its just basic recursion. Its a variant of standard version of Josephus problem.

ll compute(ll n,ll k,ll orig,ll sign){

	if(n==1)
		return 1;
	if(sign==1){
		ll val=compute(n-1,k+orig,orig,0);
		val-=1;
		if(val==0)
			k--;
		else
			k+=val;
		k%=n;
		k+=n;
		k%=n;
		val=k;
		//cout<<val<<" "<<n<<endl;
		if(val==0){
			return n;
		}
		return val;
	}
	else{
		ll val=compute(n-1,k+orig,orig,1);
		val+=((n-k+2)%n +n)%n;
		val%=n;
		val+=n;
		val%=n;
		//cout<<val<<endl;
		if(val==0){
			return n;
		}
		return val;
	}

}
int main(){
    std::ios::sync_with_stdio(false); 
    ll t;
    cin>>t;
    while(t--){
    	ll n,k;
    	ll sign=0;
    	cin>>n>>k;
    	if(k>0){
    		sign=1;
    	}
    	if(k<0){
    		k*=-1;
    		sign=0;
    	}
    	cout<<compute(n,k,k,sign)<<endl;
    }
}

get_ac function takes int k, while it overflows in main — various similar mistakes like this. I just simulated everything using BIT and it worked fine.

Read up on [Partition Function](https://en.wikipedia.org/wiki/Partition_(number_theory)#/Generating_function). You can calculate P(n) in O(sqrtN) using generalized pentagonal numbers. Then query for N, M reduces to range product of P(i), for i over the range [M, M+N-1] which you can do in O(1). Overall time complexity is O(NsqrtN + Q).

Let A(n) be the number of ways to distribute n sweets . Then A(n) = A(n - 1) + A(n - 2) - A(n - 5) - A(n - 7).... i.e where X(i) is the ith pentagonal number. Rest is just building prefix product of this array.

My solution with space complexity passed in Java. Was this expected or the time limit was bit too relaxed for Java?

See this code — https://www.codechef.com/viewsolution/13376017

If the intervals intersect, it is the right end point of the interval that ends first. Else, let [a,b] be the first interval and [l,r] the second with b<r. Consider the naive solution of checking every number from b to 1 in decreasing order. What is the condition for a given x? It is that a multiple of x lies both in [a,b] and [l,r] => (a-1)/x<b/x and (l-1)/x<r/x. Now, consider x' such that x' = x-1 and b/x = b/x' and r/x = r/x' then (a-1)/x'>=(a-1)/x, so there is no need to check x'. So from a given x we need to check only next smaller number x' such that b/x' or r/x' is different. This is a major optimization since there are only O(sqrt(r)) different r/x. So, from a given x next x' = max(r/(r/x+1),b/(b/x+1)). Complexity = O(sqrt(r)) for a test case.