蓝桥杯 算法提高 ADV-1170 阶乘测试 python AC

找规律题，遍历i中有几个m就加几，和m的多少次数有关

第一版👇

try:while True:n, m = map(int, input().split())ll = [i for i in range(1, n + 1) if i % m == 0]ans = len(ll)M = mwhile ll:lll = []M *= mfor i in ll:if i % M == 0:lll.append(i)ans += 1ll = lllprint(ans)
except:pass

不出意外地超时，怎么办，大脑停止思考...上网搜~~

搜不到。。。继续优化，先把m小于n的所有?次方数存到数组中，再在遍历的时候依次判断能否整除数组中的m的?次方（二次方中有两个m，三次方中有三个m，数组为[m, m^2, m^3, m^4.....]，每能整除一个数组中的数就+1），并且还能在遍历的时候直接按步长m遍历（步长m之外的数必不是m的倍数）

第二版👇

try:while True:n, m = map(int, input().split())num = 1ll = []while num * m <= n:num *= mll.append(num)ans = 0for i in range(m, n+1, m):for j in ll:if i % j == 0:ans += 1print(ans)
except:pass

似乎有所改善，但是依旧超时，而且答案似对非对...

看着数组突然想起来刚才修改的步长m，好像可以直接判断n中有几个m?次方的步长（依次判断数组中元素），第三版👇

try:while True:n, m = map(int, input().split())num = 1ll = []while num * m <= n:num *= mll.append(num)ans = 0for i in ll:ans += n // iprint(ans)
except:pass

好，能秒出答案了，欸，为什么0分，下载测试点看看？一看吓一跳，答案一堆错的，但是仔细观察发现好像答案都是在测试点里的，但是顺序不一样，开始怀疑python会不会在输出的时候先把用时慢的输出了，于是把所有输入保存到列表里，输入完了再开始运行，但是还是不对...在观察许久后发现，系统测试答案好像不太对，但是好像又有点规律，然后发现不知道为什么系统每两次输入才输出一个答案......（被这东西卡了，逆天）

最终AC版👇

arr = []
try:while True:n, m = map(int, input().split())arr.append((n, m))
except:pass
step = 1
for n, m in arr:step += 1if step % 2 == 0:continuenum = 1ll = []while num * m <= n:num *= mll.append(num)ans = 0for i in ll:ans += n // iprint(ans)