rasta-and-darie

A Darie is a special circle. Numbers 1, 2, ..., n are written clockwise around this circle in order. You can stand on a number! Initially Rasta is on number 1. In each step, he jumps exactly p numbers clockwise. For example if n = 3 and he is standing on number 1:

If p = 1 then he jumps to number 2.

Or if p = 2 he jumps to number 3.

He does this until he reaches a number he's been on before (for example, if n = 3, p = 1 he stops after three jumps).

Then he writes down the numbers he had been on, as a sequence s in increasing order.

He's not a Mr.Memmory, so he can't remember this sequence. He asks you to help him by telling him the k-th number in this sequence (or -1 if size of s is less than k).

Input format
The first line of input contains an integer t, the number of testcases (1 ≤ t ≤ 10^5).

Each testcase is given in one line, which contains three integers n, p, k (2 ≤ n ≤ 10^6, 1 ≤ p ≤ n - 1, 1 ≤ k ≤ 10^6).

Output format
Print the answer of each testcase in one line.

SAMPLE INPUT
3
12 5 3
12 3 2
3 2 2

SAMPLE OUTPUT
3
4
2

Source: hackerearth | Difficulty: EASY
Tags: Number theory


Solutions:
def gcd(a,b):
	if b==0:
		return a
	else:
		return gcd(b,a%b)

t=int(eval(input()))

while t>0:
	n,p,k=input().split(' ')
	a=[1,1]
	n=int(n)
	p=int(p)
	k=int(k)
	if gcd(n,p)==1:
		if k>n:
			res=-1
		else:
			res=k
	else:
		temp=gcd(n,p)
		if k>(n/temp):
			res=-1
		else:
			res=(temp*(k-1))+1
	print(res)
	t=t-1


def gcd(a,b):
	if a%b ==0:
		return b
	return gcd(b,a%b)

t = int(eval(input()))
while t > 0:
	n,p,k = [int(i) for i in input().split()]
	cd = gcd(n,p)
	res = 1 + (k-1)*cd
	if res <= n:
		print(res)
	else:
		print(-1)
	t -= 1


def hcf(p , q):
	r = 1
	while(r != 0):
		r = p%q

		p = q
		q = r

	return p
		
t = int(input())

for a in range(t):
	temp = input().split(" ")
	n = int(temp[0])
	p = int(temp[1])
	k = int(temp[2])

	if ((n%p) == 0):
		l = n / p
		
		if k <= l :
			print(1 + p*(k - 1))
		else :
			print("-1")

	else:
		h = hcf(n ,p)
		
		if (h == 1):

			l = n
			
			if k <= l :
				print(k)
			else :
				print("-1")

		else :

			l = n / h

			if k <= l :
				print(1 + h*(k - 1))
			else :
				print("-1")