PAT 乙级题目讲解：1017《A除以B》

✅ PAT 乙级题目讲解：1017《A除以B》

📌摘要：本文深入讲解 PAT 乙级 1017 题《A除以B》的求解方法，通过字符串逐位处理模拟大整数除以一位正整数。文章涵盖题目简介、样例分析、解题思路拆解、完整 C++ 代码、常见错误提醒、复杂度分析及思维拓展，系统梳理了高精度除法的核心要点。

🧩 题目简介

给定两个正整数AAA和BBB，其中：

• AAA是不超过1000 位的超大正整数；

• BBB是一位正整数。

要求输出商数QQQ和余数RRR，使得A=B×Q+RA = B \times Q + RA=B×Q+R成立。

由于AAA过大，无法使用常规整型变量处理，因此需使用字符串进行逐位除法模拟。

🧪 样例分析

输入样例 1：

123456789050987654321 7

• 模拟除法操作，逐位计算商数：
  • 高位不足除以777，继续与下一位拼接；
  • 直到被除数大于等于777，可计算一位商并更新余数。
  • 逐步竖式模拟除法过程：

• 最终商Q=17636684150141093474Q = 17636684150141093474Q=17636684150141093474，余数R=3R = 3R=3。

输出：

17636684150141093474 3

🔍 解题思路

本题属于大整数除法模拟问题，整体流程如下：

1. 将超大整数AAA以字符串形式读入，转成整型数组处理；
2. 定义初始余数r=0r = 0r=0；
3. 从左至右逐位处理字符型数字，模拟“手算除法”过程：
   • 当前数位参与计算的值为：r×10+当前数字r \times 10 + 当前数字r×10+当前数字；
   • 当前位商为：⌊r×10+当前数字B⌋\left\lfloor \frac{r \times 10 + 当前数字}{B} \right\rfloor⌊Br×10+当前数字​⌋；
   • 更新余数为上式的模；
4. 所有位处理完成后，输出拼接得到的商QQQ与最终余数RRR。

📎 变量说明

✅ Step 1：读取与预处理输入

• 用字符串读入大整数AAA，用整型变量读入BBB；

• 将字符串逐位转为整型数组na[]。

  string a;intna[1005],b,t,r,q[1005];...// 1. 把 a -> na[i]intlen=a.size();for(inti=0;i<len;i++){na[i]=a[i]-'0';}

✅ Step 2：模拟除法过程

对AAA的每一位进行以下操作：

1. 构造当前被除数段t=r×10+na[i]t = r \times 10 + na[i]t=r×10+na[i]；

2. 计算当前位商：q[i]=t÷bq[i] = t \div bq[i]=t÷b；

3. 更新余数：r=t mod br = t \bmod br=tmodb。

// 2. for 逐位模拟计算 -> q[i]for(inti=0;i<len;i++){t=r*10+na[i];// 当前被除数段q[i]=t/b;// 当前位商r=t%b;// 余数}

✅ Step 3：去除前导零并输出

• 从q[0]q[0]q[0]开始，找到第一个非 0 的位置kkk；

• 从q[k]q[k]q[k]到q[len−1]q[len-1]q[len−1]依次输出；

• 最后输出空格和余数rrr。

  // 3. 去前导 0intk=0;while(!q[k]&&k<len-1){k++;}// 4. 输出for(inti=k;i<len;i++){cout<<q[i];}cout<<" "<<r;

✅ 完整代码

#include<bits/stdc++.h>usingnamespacestd;string a;intna[1005],b,t,r,q[1005];intmain(){cin>>a>>b;// 1. 把 a -> na[i]intlen=a.size();for(inti=0;i<len;i++){na[i]=a[i]-'0';}// 2. for 逐位模拟计算 -> q[i]for(inti=0;i<len;i++){t=r*10+na[i];q[i]=t/b;r=t%b;}// 3. 去前导 0intk=0;while(!q[k]&&k<len-1){k++;}// 4. 输出for(inti=k;i<len;i++){cout<<q[i];}cout<<" "<<r;return0;}

🚧 常见错误提醒

✅ 总结归纳

📌 核心方法总结

• 高精度除法的竖式模拟；
• 商数数组逐位构建；
• 余数逐步更新传递。

📋 技术要点回顾

• 使用字符串 + 数组存储超大整数；
• 手动模拟除法的每一位除、余过程；
• 去除前导 0 的实现技巧。

📊 复杂度分析

• 时间复杂度：O(n)\mathcal{O}(n)O(n)
• 空间复杂度：O(n)\mathcal{O}(n)O(n)

其中nnn为大整数AAA的位数（最长 1000 位）。

🧠 思维拓展

• 扩展到支持小数除法（输出若干位小数）；
• 实现高精度加减乘除统一框架；
• 封装为高精度类支持多种运算符重载。