**Problem link:**

Practice

Contest link

Author: Vinay Kushwaha

Tester: Ujjawal Gupta

Editorial: Vinay Kushwaha

**Difficulty:**

Easy

**Prerequisite:**

Basic Maths, C++ stl.

**Problem Statement :-**

In this problem you are given two integers n and k and all the numbers are arranged in a circle in order 1 to n (in clockwise direction) . You have to choose two numbers at index i and j such that j=i+1 if i<n and j=1 if i=n . If a[i]<a[j] you have to do a[i]=a[j]%k.

**Algorithm:-**

If we observe the question carefully we can see that all the numbers are arranged in ascending order except the indexes i=n and j=1 So if we start taking mod with we will get a pattern like [2,3,…,0,1,2,3,…0,…n] if k>1 and if k=1 it will be [0,0,0,…n].

For k=1 we can do

ans=n

For k>1

We can see the the part [2,3,…0] will repeat (n/k) times

so we can find the sum of that part using

k–;

sum_k=(k*(k+1)/2);

sum=(sum_k*(n/k));

and the remaining part sum by

rem=n%k

sum_rem=(rem*(rem+1)/2);

ans=sum_rem+sum_part

at last we have to subtract -1 from the ans because we are not getting -1 in starting and +n in the answeer for i=n and j=1.