-
Notifications
You must be signed in to change notification settings - Fork 0
/
Boston Red Socks.py
81 lines (70 loc) · 1.66 KB
/
Boston Red Socks.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import math
def gcd(x, y):
if y == 0:
return x
return gcd(y, x % y)
while True:
flag = False
p, q = map(int, input().split())
if p + q == 0:
break
gd = gcd(p, q)
# edge case
if p == 0:
print("0 2")
continue
if p == q:
print("2 0")
continue
p //= gd
q //= gd
for i in range(3, 50001):
tem = i * (i - 1) * p
if tem % q != 0:
continue
tem //= q
mid, l, r = 0, 1, i
while l < r:
mid = (l + r) // 2
M = mid * (mid - 1)
if M < tem:
l = mid + 1
elif M > tem:
r = mid
else:
flag = True
break
if flag:
print(mid, i - mid)
else:
print("impossible")
# if i * (i - 1) % q != 0:
# continue
# j = i * (i - 1) // q * p
# tmp = int(math.sqrt(j + 0.5))
# if tmp * (tmp + 1) != j:
# continue
# if tmp >= 1:
# break
# if i == 50001:
# print("impossible")
# else:
# print(tmp + 1, i - tmp - 1)
#
# for total in range(3, 50001):
# N = total * (total - 1) * P
# if N % Q != 0:
# continue
# N //= Q
# l, r = 1, total
#
# while l < r:
# m = (l + r) // 2
# M = m * (m - 1)
# if M < N:
# l = m + 1
# elif M > N:
# r = m
# else:
# flag = True
# break