题目分析

本题要求找到最大的 $k$，使得 $k \times b$ 的价格在不超过 $a$ 的情况下，末尾有尽可能多的连续数字 $d$。

关键观察：价格 $k \times b$ 末尾有 $p$ 个连续的 $d$，等价于：

$$k \times b \equiv d \times \frac{10^p - 1}{9} \pmod{10^p} $$

算法思路

核心思想：数论 + 二分答案

主要步骤：

1. 特殊情况处理 ($d = 0$)

   • 当 $d = 0$ 时，问题转化为找到最大的 $p$ 使得 $k \times b$ 末尾有 $p$ 个0
   • 这等价于 $k \times b$ 能被 $10^p$ 整除
   • 通过分解 $b$ 的质因数（2和5的因子）来优化计算

2. 一般情况 ($d \neq 0$)

   • 使用二分答案确定最大的连续 $d$ 的数量 $p$
   • 对于每个 $p$，检查是否存在 $k$ 满足条件

数学推导

对于 $d \neq 0$ 的情况，我们需要解方程：

$$k \times b \equiv d \times \frac{10^p - 1}{9} \pmod{10^p} $$

等价于：

$$k \times b \times 9 \equiv d \times (10^p - 1) \pmod{9 \times 10^p} $$

进一步转化为：

$$k \times (9b) \equiv d \times (10^p - 1) \pmod{9 \times 10^p} $$

算法实现细节

1. 大数处理

由于 $a$ 可以达到 $10^{10000}$，需要使用自定义的大数类：

struct node {
    int st[MAXN], leng;
    // 支持大数的比较、减法、除法等操作
};

2. 扩展欧几里得算法

用于求解线性同余方程：

int exgcd(int a, int b, int &x, int &y) {
    if (!b) return x = 1, y = 0, a;
    int d = exgcd(b, a % b, y, x);
    y -= x * (a / b);
    return d;
}

3. 二分答案框架

int L = 0, R = 1e4, res = 0;
while (L <= R) {
    int mid = L + R >> 1;
    if (checkit(mid)) res = mid, L = mid + 1;
    else R = mid - 1;
}

4. 检查函数 checkit(p)

对于给定的 $p$，检查是否存在满足条件的 $k$：

• 计算 $v = 10^p \bmod (9B)$
• 使用扩展欧几里得解方程
• 验证解是否在约束范围内

代码结构

主要组件

1. 大数类 node

   • 支持比较、减法、除法运算
   • 处理高达 $10^{10000}$ 的大数

2. 核心检查逻辑

   bool checkit(int p) {
       // 模运算和方程求解
       // 验证解的存在性和有效性
   }
   

3. 特殊情况处理 ($d = 0$)

   if (!D) {
       // 处理末尾0的特殊情况
       // 基于2和5的因子分解
   }
   

复杂度分析

• 时间复杂度：$O(P \times \text{大数操作复杂度})$，其中 $P$ 是二分的范围
• 空间复杂度：$O(\text{大数长度})$，主要用于存储大数 $a$

关键技巧

1. 模运算优化：通过模 $9B$ 来减少计算量
2. 扩展欧几里得：高效求解线性同余方程
3. 大数运算：自定义大数类处理超大输入
4. 二分答案：将最优解问题转化为判定问题

样例分析

样例1：$b=57, d=9, a=1000$

• 最大连续9的数量为2（对应 $k=7$, $7 \times 57 = 399$）

样例2：$b=57, d=4, a=40000$

• 最大连续4的数量为3（对应 $k=692$, $692 \times 57 = 39444$）

样例3：$b=57, d=4, a=39000$

• 最大连续4的数量为2（$k=692$ 的价格超过限制）

该算法通过巧妙的数学转化和高效的大数处理，成功解决了这个具有挑战性的数论问题。