good-times-vs-bad-times-3

Chandan, our problem moderator, recently got a digital clock as a birthday present. A digital clock shows time in the format HH:MM:SS, where HH, MM, SS represents hours , minutes, and seconds respectively. It is a 24 hour clock and so the day starts at 00:00:00 hours while it ends at 23:59:59.

We all know how punctual and particular Chandan is about each and every second of his life. One sunny day, at his leisure, when he was fiddling with his clock, he discovered that a second was good for him if none of the HH, MM\; and \; SS at that second was divisible by the same prime number, i.e. it is bad if all of them give 0 as a remainder when divided by the same prime number. 

Given a time of a day, Chandan now wants to count the number of good times and bad times from that instance till the end of the day (23:59:59). 

Input & Output:
The first line of the input contains the number of test cases T. T test cases follow and each test contains a line HH MM SS, the time from which he wants to count till the end of that day. 

For each test case, output a ratio in the format "B:G" (quotes for clarity), where G is the the number of good seconds and B is the number of bad seconds for Chandan. Express the ratio B : G in its lowest terms, i.e. it should not have any common factor.

Constraints

1 ≤ T ≤ 10 ^ 5
00 ≤ HH < 24
00 ≤ MM < 60
00 ≤ SS < 60  

SAMPLE INPUT
2
23 59 58
23 46 22

SAMPLE OUTPUT
0:2
1:408

Explanation

1) In the first case, there 23:59:59 is good because there is no prime number that leaves a remainder 0 when it divides all of them. Similarly 23:59:58 is also good. Hence the answer is 0:2

2) In the second case, there are two bad numbers, 23:46:23 (leaves remainder 0 when divided by 23) and 23:46:46. There are 816 good numbers. Hence the answer is 2:816 => 1:408

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Dynamic programming

Mathematics


Solutions:
primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
arr=[0]*100000

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

def to_sec(h,m,s):
	return (h*60*60) + (m*60) + s
def check_div(h,m,s):
	for e in primes:
		if h%e==0 and m%e==0 and s%e==0:
			return False
	return True

for h in range(24):
	for m in range(60):
		for s in range(60):
			if check_div(h,m,s):
				arr[to_sec(h,m,s)]+=1

for i in range(len(arr)-2,-1,-1):
	arr[i]+=arr[i+1]
	
t=int(input())
for i in range(t):
	h,m,s=(int(e) for e in input().split())
	sec=to_sec(h,m,s)
	good=arr[sec]
	bad=(24*60*60)-sec-good
	temp=gcd(bad,good) if bad!=0 else 1
	print("%d:%d"%(bad/temp,good/temp))
			



from fractions import *

tot = 86400
vals = [0]*tot


def flat(x,y,z):
	return ((60*60)*x) + (60*y) + z

def chk(x,y,z):
	if gcd(gcd(x,y),z) != 1:
		return 1
	return 0

def process():
	global tot
	global vals
	
	for x in range(24):
		for y in range(60):
			for z in range(60):
				vals[flat(x,y,z)] = chk(x,y,z)
				#if vals[flat(x,y,z)] == 1:
				#	print x,y,z
				
	for k in range(tot-2,-1,-1):
		vals[k] += vals[k+1]
		
def solve():
	global tot
	global vals
	nums = [int(x) for x in input().split()]
	
	idx = flat(nums[0],nums[1],nums[2])
	
	bad_nums = vals[idx]
	good_nums = tot - bad_nums - idx
	
	if bad_nums != 0:
		div = gcd(bad_nums,good_nums)
	
		bad_nums /= div
		good_nums /= div
	
	print("%d:%d"%(bad_nums,good_nums))
	
	

	
def main():
	t = int(input())
	process()
	for _ in range(t):
		solve()
		
main()
#process()


from fractions import gcd,Fraction
HH = 0
MM = 0
SS = 0
bad = 0
good = 0
badarr = []
goodarr = []
while(HH<24 and MM <60 and SS<60):
	goodarr.append(good)
	badarr.append(bad)	
	gcdHM = gcd(HH,MM)
	gcdGS = gcd(gcdHM,SS)
	if(gcdGS==1):# or HH<=1 or MM<=1 or SS<=1):
		good+=1		
	else:
		bad+=1		
	SS+=1
	if(SS==60):
		MM+=1
		SS=0
	if(MM==60):
		HH+=1
		MM=0
		SS=0

reqdict = {}
larr = len(badarr)
for i in range(larr):
	b = bad-badarr[i]
	g = good-goodarr[i]
	if(g!=0 and b!=0):
		f = Fraction(b,g)
		reqdict[i]=str(f.numerator) + ":"+str(f.denominator)
	else:	
		reqdict[i]=str(b) + ":" + str(g)
	
t = int(eval(input()))
for i in range(t):
	h,m,s=list(map(int,input().split()))
	tosecs = h*60*60 + m*60 + s
	print(reqdict[tosecs])