题解 | 细胞增殖 | Python3 二分查找

N, M = map(int, input().split())
arr = list(map(int, input().split()))

# Algo
for _ in range(M):
    B, S = map(int, input().split())
    left, right = 0, N
    all_cnt, peak_cnt = 0, 0
    for t in range(1, 99999):
        C = B**t + S
        right = N-1
        if C > arr[-1]:  # Quick jump.
            left = N
        while left <= right:
            mid = (left + right) // 2
            val = arr[mid]
            if C < val:
                right = mid - 1
            elif C > val:
                left = mid + 1
            else:
                # Count identical value sequence.
                cnt = 0
                i = mid
                while i >= 0 and arr[i] == val:
                    i -= 1
                    cnt += 1
                i = mid+1
                while i < N and arr[i] == val:
                    i += 1
                    cnt += 1
                left = i
                all_cnt += cnt
                peak_cnt = max(peak_cnt, cnt)
                break
        # No more data.
        if left >= N or B < 2:
            print(all_cnt, peak_cnt)
            break