细胞增殖

题目分析

细胞种群数量满足公式 $N = a^n + b$ ，其中 $a$ 为增殖基数， $b$ 为稳定基数， $n$ 为增殖周期（正整数， $n \ge 1$ ）。

给定 $m$ 条升序排列的观测记录和 $q$ 组假说 $(a, b)$ ，对每组假说需要回答：

有多少条记录能被该假说解释（即存在正整数 $n$ 使 $N_i = a^n + b$ ）
所有合法周期值中，单个 $n$ 对应的最多记录数（增殖峰值）

思路

枚举幂次 + 二分查找

关键观察：对于 $a \ge 2$ ， $a^n$ 增长极快， $n$ 最多只有约 $\log_a(\text{maxN})$ 个取值。例如 $a = 2$ 时 $n$ 不超过 $62$ 。因此可以枚举所有可能的 $n$ ，计算 $\text{target} = a^n + b$ ，然后在有序的观测数组中二分查找该值出现的次数。

对 $a = 0$ 和 $a = 1$ 需要特殊处理：

$a = 0$ ： $0^n = 0$ （ $n \ge 1$ ），所以 $N = b$ 。所有值等于 $b$ 的记录都匹配，且它们对应任意 $n$ ，因此总数和峰值均为该值的出现次数。
$a = 1$ ： $1^n = 1$ （ $n \ge 1$ ），所以 $N = b + 1$ 。逻辑同上。
$a \ge 2$ ：从 $a^1$ 开始逐步乘以 $a$ ，每次用二分统计 $a^n + b$ 在数组中的出现次数，累加总数并更新峰值。当 $a^n$ 超过 $2 \times 10^{18}$ 时停止，防止溢出。

以样例 2 验证： 记录 $= [2, 3, 4, 5, 5, 6, 7, 7, 9, 16, 17]$ ，假说 $(a=2, b=1)$ ：

$n=1$ ： $\text{target} = 2^1 + 1 = 3$ ，出现 $1$ 次
$n=2$ ： $\text{target} = 2^2 + 1 = 5$ ，出现 $2$ 次
$n=3$ ： $\text{target} = 2^3 + 1 = 9$ ，出现 $1$ 次
$n=4$ ： $\text{target} = 2^4 + 1 = 17$ ，出现 $1$ 次

总数 $= 1 + 2 + 1 + 1 = 5$ ，峰值 $= 2$ ，输出 5 2，与期望一致。

复杂度

时间复杂度： $O(q \cdot \log_a(\text{maxN}) \cdot \log m)$ ，每组假说枚举最多约 $60$ 个幂次，每次二分 $O(\log m)$
空间复杂度： $O(m)$ ，存储观测记录数组

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, q;
    scanf("%d%d", &m, &q);
    vector<long long> rec(m);
    for (int i = 0; i < m; i++) scanf("%lld", &rec[i]);

    while (q--) {
        long long a, b;
        scanf("%lld%lld", &a, &b);

        long long total = 0, peak = 0;

        auto countVal = [&](long long target) -> long long {
            return (long long)(upper_bound(rec.begin(), rec.end(), target) -
                               lower_bound(rec.begin(), rec.end(), target));
        };

        if (a == 0) {
            long long cnt = countVal(b);
            total = cnt;
            peak = cnt;
        } else if (a == 1) {
            long long cnt = countVal(b + 1);
            total = cnt;
            peak = cnt;
        } else {
            // a >= 2，枚举 a^1, a^2, ...
            long long pw = 1;
            for (int n = 1; n <= 62; n++) {
                if (pw > (long long)2e18 / a) break;
                pw *= a;
                long long target = pw + b;
                long long cnt = countVal(target);
                total += cnt;
                peak = max(peak, cnt);
            }
        }

        printf("%lld %lld\n", total, peak);
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        long[] rec = new long[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            rec[i] = Long.parseLong(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());

            long total = 0, peak = 0;

            if (a == 0) {
                long cnt = countVal(rec, b);
                total = cnt;
                peak = cnt;
            } else if (a == 1) {
                long cnt = countVal(rec, b + 1);
                total = cnt;
                peak = cnt;
            } else {
                long pw = 1;
                for (int n = 1; n <= 62; n++) {
                    if (pw > (long) 2e18 / a) break;
                    pw *= a;
                    long target = pw + b;
                    long cnt = countVal(rec, target);
                    total += cnt;
                    peak = Math.max(peak, cnt);
                }
            }

            sb.append(total).append(' ').append(peak).append('\n');
        }
        System.out.print(sb);
    }

    static long countVal(long[] arr, long target) {
        return upperBound(arr, target) - lowerBound(arr, target);
    }

    static int lowerBound(long[] arr, long target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    static int upperBound(long[] arr, long target) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline

def main():
    m, q = map(int, input().split())
    rec = list(map(int, input().split()))

    out = []
    for _ in range(q):
        a, b = map(int, input().split())
        total = 0
        peak = 0

        if a == 0:
            cnt = bisect_right(rec, b) - bisect_left(rec, b)
            total = cnt
            peak = cnt
        elif a == 1:
            target = b + 1
            cnt = bisect_right(rec, target) - bisect_left(rec, target)
            total = cnt
            peak = cnt
        else:
            pw = 1
            for n in range(1, 63):
                if pw > 2 * 10**18 // a:
                    break
                pw *= a
                target = pw + b
                cnt = bisect_right(rec, target) - bisect_left(rec, target)
                total += cnt
                peak = max(peak, cnt)

        out.append(f"{total} {peak}")

    sys.stdout.write('\n'.join(out) + '\n')

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const [m, q] = lines[idx++].split(' ').map(Number);
    const rec = lines[idx++].split(' ').map(BigInt);

    function lowerBound(arr, target) {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >>> 1;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    function upperBound(arr, target) {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >>> 1;
            if (arr[mid] <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    function countVal(target) {
        return upperBound(rec, target) - lowerBound(rec, target);
    }

    const out = [];
    for (let i = 0; i < q; i++) {
        const parts = lines[idx++].split(' ').map(BigInt);
        const a = parts[0], b = parts[1];
        let total = 0, peak = 0;

        if (a === 0n) {
            const cnt = countVal(b);
            total = cnt;
            peak = cnt;
        } else if (a === 1n) {
            const cnt = countVal(b + 1n);
            total = cnt;
            peak = cnt;
        } else {
            let pw = 1n;
            const LIMIT = 2000000000000000000n;
            for (let n = 1; n <= 62; n++) {
                if (pw > LIMIT / a) break;
                pw *= a;
                const target = pw + b;
                const cnt = countVal(target);
                total += cnt;
                peak = Math.max(peak, cnt);
            }
        }

        out.push(`${total} ${peak}`);
    }
    console.log(out.join('\n'));
});