题解 | 细胞增殖

#include <bits/stdc++.h>
using namespace std;
long long power(int a, int b) {
    //计算a的b次方
    long long result = 1;
    while (b > 0) {
        result *= a;
        b--;
    }
    return result;
}
int main() {
    int N, M;
    cin >> N >> M;
    int* C = new int [N];
    int* B = new int [M];
    int* S = new int [M];
    for (int i = 0; i < N; ++i)
        cin >> C[i];
    for (int i = 0; i < M; ++i) {
        cin >> B[i] >> S[i];
    }
    for (int i = 0; i < M; ++i) {
//      cout<<"第"<<i<<"批符合要求的：";
        int t = 1;
        int Max = 0;
        int count = 0;
        if (B[i] > 1) {
		  //基数大于1
		  //二分查找
            int low = 0;
            while (1) {
                long long temp = power(B[i], t) + S[i];
                if (temp > C[N - 1])
                    break;
                for (int high = N - 1; low <= high; ) {
                    int mid = (low + high) / 2;
                    int length = 0;
                    if (temp == C[mid]) {
                        length++;
                        count++;
                        int k = mid + 1;
                        while (k < N && C[k] == temp) {
                            k++, length++, count++;
                        }
                        int l = mid - 1;
                        while (l >= 0 && C[l] == temp)
                            l--, length++, count++;
                        if(length > Max)
                            Max = length;
                        break;
                    }else if(temp > C[mid]){
                        low = mid + 1;
                    }else high = mid - 1;
                }
                t++;
            }
        } else if (C[N - 1] >= S[i] + B[i]) {
		  //基数为0或者1
            for (int j = 0; j < N; ++j) {
                if (C[j] == S[i] + B[i]) {
                    count++;
                    Max++;
                }
            }
        }
//        cout<<endl;
        cout << count << " " << Max << endl;
    }
}
// 64 位输出请用 printf("%lld")