> "Even a broken clock is right twice a day"

For those unfamiliar with the above proverb, the statement refers to a stopped 12 hour clock. The time it shows happens to coincide with the true time twice every 24 hours.

Chef has a useless clock which does not run properly. More specifically, it runs at $K$ times the rate of a correct clock, where $K \ne 1$. It may even be that $K$ is negative, which means the clock runs backwards. Chef also has a clock which precisely shows the current time without error.

At 12 am on day $1$ Chef sets the useless clock to point to 12:00. Of course Chef's correct clock already points to 12:00. Chef wonders on which day the time shown by the useless clock will coincide with the correct clock for the $N^{th}$ time. 

Can you help him find the answer without having to wait for that many days?   
Note that 12 am of day $d$ is considered the first instant of day $d$. Since the clocks initially show the same time at 12 am of day $1$, that is counted as the first time they coincide.

------ Input: ------
First line will contain $T$, the number of test cases.
The next $T$ lines each contain 3 integers $p$, $q$ and $N$, where $\frac{p}{q} = K$.

------ Output: ------
For each test case, output a single integer which is the day on which the times of the clocks coincide for the $N^{th}$ time.

------ Constraints  ------
$1 ≤ T ≤ 10^{5}$
$-100 ≤ K ≤ 100$
$K \ne 1$
$1 ≤ q ≤ 10^{4}$
$1 ≤ N ≤ 10^{6}$

------ Sample Input: ------
4
0 1 5
-1 2 3
2 1 10
99 100 2

------ Sample Output: ------
3
1
5
51
	
------ Explanation: ------
Case 1: Here $K = 0$. A broken clock is right twice a day. So it will be right for the fifth time on day $3$.
Case 2: Here $K = -1/2$. The clock moves backwards at half the rate of the correct clock. The time displayed will coincide with the true time first at 12 am, then at 8 am and for the third time at 4 pm on day $1$.

Difficulty: HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
from math import ceil, floor
for _ in range(int(input())):
	(p, q, n) = list(map(int, input().split()))
	r = floor(q * (n - 1) / (abs(p - q) * 2)) + 1
	print(r)


for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(int(0.5 * q * (n - 1) / abs(p - q)) + 1)


t = int(input())
for _ in range(t):
	kn = list(map(int, input().split()))
	p = kn[0]
	q = kn[1]
	n = kn[2]
	ans = q * 12 * (n - 1) // (abs(q - p) * 24)
	print(ans + 1)


from math import gcd

class fraction:

	def __init__(self, n, d=1):
		if not (type(n) == int and type(d) == int):
			raise ArithmeticError()
		sign = 1 if n * d > 0 else -1
		self.num = sign * abs(n)
		self.den = abs(d)

	def __add__(self, o):
		return fraction(self.num * o.den + self.den * o.num, self.den * o.den)

	def __neg__(self):
		return fraction(-1 * self.num, self.den)

	def __sub__(self, o):
		return fraction(self.num * o.den - self.den * o.num, self.den * o.den)

	def __mul__(self, o):
		return fraction(self.num * o.num, self.den * o.den)

	def __truediv__(self, o):
		return fraction(self.num * o.den, self.den * o.num)

	def __floordiv__(self, o):
		f = self / o
		return fraction(f.num // f.den)

	def simplify(self):
		g = gcd(self.num, self.den)
		self.num /= g
		self.den /= g

	def abs(self):
		return fraction(abs(self.num), self.den)

	def value(self):
		if self.den == 1:
			return self.num
		return self.num / self.den

	def __str__(self):
		return str(self.num) + '/' + str(self.den)

def main():
	t = int(input())
	while t > 0:
		ONE = fraction(1)
		ZERO = fraction(0)
		t -= 1
		(a, b, k) = [fraction(int(i)) for i in input().split()]
		relSpd = (a / b - ONE).abs()
		k -= ONE
		timeForOneCycle = ONE / relSpd * fraction(12)
		totTimeinHrs = timeForOneCycle * k
		print((totTimeinHrs // fraction(24) + ONE).value())
main()


for t in range(int(input())):
	s = input().split()
	p = int(s[0])
	q = int(s[1])
	n = int(s[2])
	t = (n - 1) * q / 2
	if p - q > 0:
		t = t // (p - q)
	else:
		t = t * -1 // (p - q)
	print(int(t + 1))


from math import gcd
for _ in range(int(input())):
	(p, q, n) = map(int, input().split())
	ans = (n - 1) * 12 * q // (abs(p - q) * 24) + 1
	print(ans)


import math
t = int(input())
for i in range(t):
	(p, q, n) = map(int, input().split())
	n -= 1
	val = n * q
	val /= abs(p - q)
	val /= 2
	if val - math.floor(val) < 1e-06:
		val += 1
	print(math.ceil(val))


from math import floor
from fractions import Fraction as F
t = int(input())
for case in range(t):
	(p, q, N) = map(int, input().split())
	speed = abs(1 - F(p, q))
	time = F(1, 2) / speed * (N - 1)
	print(floor(time + 1))


import math
_ = int(input())
for __ in range(_):
	(p, q, n) = map(int, input().split())
	n -= 1
	val = n * q
	val /= abs(p - q)
	val /= 2
	if val - math.floor(val) < 1e-06:
		val += 1
	print(math.ceil(val))


import math
t = int(input())
for tst in range(t):
	(p, q, n) = map(int, input().split())
	k = p / q
	x = math.floor(abs(q * (12 * (n - 1)) / (q - p)) / 24 + 1)
	print(x)


t = int(input())
while t:
	(p, q, N) = map(int, input().split())
	upp = q * 12 * (N - 1)
	down = abs(q - p)
	ans = upp // down // 24 + 1
	print(ans)
	t -= 1


import math
for __ in range(int(input())):
	(p, q, n) = map(int, input().split())
	print(math.floor(abs(12 * (n - 1) * q / (q - p)) / 24) + 1)


import math

def main():
	for x in range(int(input())):
		testcases()

def testcases():
	(p, q, N) = [int(x) for x in input().split()]
	k = N - 1
	t = 12 * k * q / (q - p)
	print(math.floor(abs(t) / 24) + 1)
main()