腾讯0901笔试题第二题求思路

O(n*logn)复杂度的 import sys if __name__ == "__main__":     t,k=sys.stdin.readline().strip().split()     t,k=int(t),int(k)     for _ in range(t):         a,b=sys.stdin.readline().strip().split()         a,b=int(a),int(b)         times=0         count=0         for i in range(a,b+1):             white = 0             times=0             while white<=i:                 if white==0:                     count+=1                 else:                     count+=i-white+1                 times+=1                 white = times * k         print(count) 简化为O(n)的代码： import sys if __name__ == "__main__":     t,k=sys.stdin.readline().strip().split()     t,k=int(t),int(k)     for _ in range(t):         a,b=sys.stdin.readline().strip().split()         a,b=int(a),int(b)         count=0         for i in range(a,b+1):             n=i//k             count+=(1+n*i-(1+n)*n*k/2+n)         print(int(count)) 测试用例全过了，但是线上通过率0%。说循环有误或者算法复杂度过大。难道要O(1)的复杂度？ 求大佬解答

用dp的方法。 [t,k] = list(map(int,input().split())) maxn = int(1e5 + 100) dp = [[0]*2 for _ in range(maxn)] dp[1][1] = 1 dp[k][0] = 1 ans = [0]*maxn for i in range(1,100000):     dp[i+k][0] += (dp[i][0] + dp[i][1])     dp[i+1][1] += (dp[i][0] + dp[i][1])     ans[i] = ans[i-1] + dp[i][0] + dp[i][1] while t:     [a,b] = list(map(int,input().split()))     print(ans[b] - ans[a-1])     t -= 1 最后不知道过了多少，快要交卷了