SRM145 DIV2 500

枚举题，原题重新表述为：

求 ({frac{100x}{time} | x in (0,time)}) 集合内整数的个数

(time) 的范围不算大，直接枚举即可

优化

(整数个数=gcd(time,100)-1)

证明如下：

(frac{100x}{time}) 是整数当且仅当 (x=k imes frac{time}{gcd(time,100)}, k in Z )，则：

(egin{equation}egin{split}x &in (0, time) \ k imes frac{time}{gcd(time,100)} &in (0, time) \ k &in (0, gcd(time, 100)) end{split}end{equation})

(k) 的个数即为整数的个数

 1 class ExerciseMachine:
 2     def getPercentages(self, time):
 3         h = int(time[0:2])
 4         m = int(time[3:5])
 5         s = int(time[6:8])
 6         tot = h * 3600 + m * 60 + s
 7 
 8         counter = 0
 9         for time in range(1, tot):
10             if 100 * time % tot == 0:
11                 counter += 1
12 
13         return counter
14 
15 
16 # test
17 o = ExerciseMachine()
18 
19 # test case
20 assert(o.getPercentages("00:30:00") == 99)
21 assert(o.getPercentages("00:28:00") == 19)

View Code