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))