蓝桥杯算法改进 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 = m
        while ll:
            lll = []
            M *= m
            for i in ll:
                if i % M == 0:
                    lll.append(i)
                    ans += 1
            ll = lll
        print(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 = 1
        ll = []
        while num * m <= n:
            num *= m
            ll.append(num)
        ans = 0
        for i in range(m, n+1, m):
            for j in ll:
                if i % j == 0:
                    ans += 1
        print(ans)
except:
    pass

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

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

try:
    while True:
        n, m = map(int, input().split())
        num = 1
        ll = []
        while num * m <= n:
            num *= m
            ll.append(num)
        ans = 0
        for i in ll:
            ans += n // i
        print(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 += 1
    if step % 2 == 0:
        continue
    num = 1
    ll = []
    while num * m <= n:
        num *= m
        ll.append(num)
    ans = 0
    for i in ll:
        ans += n // i
    print(ans)