-
Notifications
You must be signed in to change notification settings - Fork 0
/
p33.py
73 lines (62 loc) · 1.52 KB
/
p33.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
# -*- coding: utf-8 -*-
"""
Created on Wed Mar 22 11:13:23 2017
@author: Refaia
"""
import time
def gcd(a, b):
while b != 0 :
a, b = b, a % b
return a
def reduce(x, y) :
newX = str(x)
newY = str(y)
for i in str(x):
if i in str(y):
newY = str(y).replace(i,'',1)
newX = str(x).replace(i,'',1)
if newX == '' :
newX = '1'
if newY == '0' :
newY = '1'
return int(newX), int(newY)
def main() :
delta = time.time()
upperLimit = 100
nonTrivialNums = []
for i in range(2, upperLimit) :
for j in range(1, i) :
if j % 10 == 0 :
continue
x, y = reduce(j, i)
if (j, i) == (x, y):
continue
if x / y == j / i :
nonTrivialNums.append((j, i))
resultX, resultY = 1, 1
for couple in nonTrivialNums :
resultX *= couple[0]
resultY *= couple[1]
denominator = resultY // gcd(resultX, resultY)
delta = time.time() - delta
return denominator, delta
print(main())
"""
BEST SOLUTION
def gcd(a, b):
while b != 0 :
a, b = b, a % b
return a
denproduct = 1
nomproduct = 1
delta = time.time()
for i in range(3,10):
for den in range(2, i) :
for nom in range(1, den) :
if ((nom * 10 + i) * den == nom * (i * 10 + den)) :
denproduct *= den
nomproduct *= nom
denproduct /= gcd(nomproduct, denproduct)
delta = time.time() - delta
print(denproduct, delta)
"""