walter-jesse-and-hcf

Walter and Jesse's friend Mike had helped them in making Crymeth and hence, they wanted to give him a share.
For deciding the share, they both decided to choose one number each, X and Y and found out that K^th Highest Common Factor of their two numbers is a good amount of Crymeth that can be given to Mike .
Walter and Jesse did this activity for D days in total. For each day, find out what quantity of Crymeth they decided to give to Mike.

Input:

First line contains a natural number D - the total number of days.
D lines follow. Each line contains three natural numbers - X, Y and K.

Output:

For each day, print the quantity given to Mike on a new line.
If the K^th HCF of X and Y does not exist, simply print "No crymeth today" (Without the quotes)

Constraints:
1 ≤ D ≤ 10^3
1 ≤ X, Y, K ≤ 10^10

SAMPLE INPUT
3
8 16 2
8 16 4
8 16 5

SAMPLE OUTPUT
4
1
No crymeth today

Explanation

1st Highest Common Factor of 8 and 16 = 8
2nd Highest Common Factor of 8 and 16 = 4
3rd Highest Common Factor of 8 and 16 = 2
4th Highest Common Factor of 8 and 16 = 1

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
from fractions import gcd
import math

def kFactorEven(a, maxA, curK, gcd, lowerList):
	if a >= maxA:
		if a == maxA and gcd % a == 0: lowerList.append(a)
		if curK > len(lowerList): return -1
		else: return lowerList[len(lowerList) - curK]
	if gcd % a == 0:
		if curK - 1 == 0: return gcd / a
		else:
			lowerList.append(a)
			return kFactorEven(a+1, maxA, curK-1, gcd, lowerList)
	else: return kFactorEven(a+1, maxA, curK, gcd, lowerList)
	
def kFactorOdd(a, maxA, curK, gcd, lowerList):
	if a >= maxA:
		if a == maxA and gcd % a == 0: lowerList.append(a)
		if curK > len(lowerList): return -1
		else: return lowerList[len(lowerList) - curK]
	if gcd % a == 0:
		if curK - 1 == 0: return gcd / a
		else:
			lowerList.append(a)
			return kFactorOdd(a+2, maxA, curK-1, gcd, lowerList)
	else: return kFactorOdd(a+2, maxA, curK, gcd, lowerList)

T = eval(input())
for _ in range(T):
	X, Y, K = list(map(int, input().strip().split()))
	gcdXY = gcd(X, Y)
	
	if gcdXY == 1:
		if K == 1: print("1") 
		else: print("No crymeth today")
		continue
	
	if K == 1:
		print(gcdXY)
		continue
	
	srGCD = math.sqrt(gcdXY)
	kthFactor = -1
	
	if gcdXY % 2 == 1:
		kthFactor = kFactorOdd(3, srGCD, K - 1, gcdXY, [1])
	else: kthFactor = kFactorEven(2, srGCD, K - 1, gcdXY, [1])
	
	if kthFactor > 0: print(kthFactor)
	else: print("No crymeth today")


from functools import reduce
def hcf(x, y):

	while(y):
		 x, y = y, x % y
	return x
def factors(n):    
	return list(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
inp1 = input()
for i in range(int(inp1)):
	inp = list(map(int,input().split(' ')))
	if inp[0] > inp[1]:
		inp[0],inp[1] = inp[1],inp[0]
	hcfs = hcf(inp[0],inp[1])
	lis = factors(hcfs)
	sortlist = sorted(lis, reverse=True)
	if inp[2]-1 < len(sortlist):
		print(sortlist[inp[2]-1])
	else:
		print("No crymeth today")


import os
import math
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def main():
	D = eval(input())
	for i in range(0,D):
		T = input()
		X = int(T.split(' ')[0])
		Y = int(T.split(' ')[1])
		K = int(T.split(' ')[2])
		X1 = list(factors(X).intersection(factors(Y)))
		# Common factors list
		if K > len(X1):
			print("No crymeth today")
		else:
			print(sorted(X1, reverse=True)[K-1])

main()