第一次在PAT乙级题库里翻到1017这道A除以B时我差点直接跳过——不就是个除法吗直到瞥见输入样例里那串二十位长的数字才意识到事情没那么简单。PAT乙级1017的题面很短给一个不超过1000位的正整数A和一个一位正整数B要求输出A除以B的商和余数。它看起来人畜无害实际是大整数运算整个章节的开端也是很多人第一次在OJ上真切体会到内置整数类型不够用的题。如果你正在准备PAT乙级或者想用C语言把高精度运算的基础补扎实这篇内容值得认真看一遍。我会把题目的核心逻辑、逐位除法的底层原理、可以直接提交的C语言代码以及我当时反复WA才排查出来的几个坑全部展开讲清楚。题目本身不难但把它吃透后面遇到高精度加法、减法、乘法你都会轻松很多。1. 题目解析A除以B究竟在考什么1.1 题面到底说了啥题面一句话就能说完。输入在一行里给出两个数A和B中间用空格隔开。A是不超过1000位的正整数B是一位正整数。要求的输出是Q和R满足A B × Q R且0 ≤ R B。注意Q和R在同一行输出中间一个空格。这里有几个容易忽略的细节。B不是0所以不存在分母为0的边界情况R是余数它一定比B小既然B是一位数R的范围就是0到8用一个普通的int变量就能存完全不需要走大数路线。而Q的位数最多是多少当B1时Q就等于A本身位数和A一样长最多1000位。输入输出格式其实比很多题都要简洁。样例输入是123456789050987654321 7样例输出是17636684150141093474 3。你自己拿计算器按一下都会发现普通计算器根本显示不完这串数这就引出了这道题真正想考的东西。1.2 这题看着简单为什么能进乙级题库因为它一上来就堵死了你走捷径的念头。第一次写这题的人十有八九会这样想定义long long a再定义int b直接a / b和a % b完事。提交之后大概率一半测试点答案错误甚至运行错误。这就是乙级题目的典型风格题面不复杂但数据范围直接把你拉到普通整数类型无法解决的层面。1017在整个乙级序列里算是一个分界线它后面跟着的高精度题基本都建立在同一套思路上——数字太长就用字符串存运算规则不变就把小学生竖式翻译成循环。不少刷题群里的同学把这道题归类为字符串处理题我觉得更准确的说法是用字符串做载体的大数除法入门题。你不需要什么高级数据结构一个字符数组加一个循环就够但前提是你得想明白除法竖式在计算机里是怎么一步步跑起来的。2. 为什么越界整数类型装不下的那900多位去哪了2.1 int和long long到底能装多少位先来算一笔账。int哪怕是无符号最大也就是2^32 - 1大约42.9亿10位数封顶。long long的上限大约是9.22 × 10^18勉强20位。unsigned long long再大一点约1.84 × 10^19同样还是20位的量级。而题目给的A最长1000位。也就是说A和能用内置整数类型直接存下的最大值之间差了大约980位的距离。这不是简单的溢出是量级上的碾压。哪怕题目只给一个20位的数字long long也会在边界上翻车给到30位市面上所有的主流语言内置整数类型没有一个能接住。类型大致范围十进制位数int-2^31 ~ 2^31 - 1最多10位unsigned int0 ~ 2^32 - 1最多10位long long-2^63 ~ 2^63 - 1最多19~20位unsigned long long0 ~ 2^64 - 1最多20位题目中的A正整数不超过1000位最多1000位这组数据摆在一起结论就很明确了存储层面必须换方案而且不是换一个更大的整数类型就能解决的得从数据结构上换思路。2.2 大数唯一靠谱的存储方式字符串既然内置整数类型全部超载那就只能用数组。每一位数字存成数组里的一个元素对C语言来说最顺手的就是字符数组。原因很简单输入输出天然就是字符串格式scanf一把梭printf也一把梭中间把字符减掉0就能得到真正的数字值。有人可能会问用int数组是不是也行当然行但要多写一段字符串转数字的逻辑最后输出商的时候还得再转换回去。用字符数组的话除法过程中每一位数字在数学计算层面是int在存储层面是char两者之间只隔一个减0和加0的距离。我习惯把这种做法理解成一种活页账本思路把大数拆成一张张活页每页只记一位数字。要算多少位就翻多少页页码没有上限内存够就用。这比一口气找一个能装下1000位整数的大箱子要现实得多。3. 逐位除法原理把竖式搬进循环里3.1 手动算一遍122除以7很多资料直接甩代码但我建议先从手算开始。小学学的竖式除法还记得吧拿122 ÷ 7走一遍流程看第一位11比7小商0余1然后把第二位2拉下来变成1212除以7商1余5再把第三位2拉下来变成5252除以7商7余3。于是竖式上得到商017余3去掉前导0最终商17、余3。这个过程中有一个关键点每一位计算时用到的被除数不是A本身剩下的那部分而是上一步留下来的余数 × 10 当前位数字。它把一次大数除法拆成了n次一位数除法。除完当前位商直接写进结果余数保留给下一位继续用。所以程序结构其实非常简单一个循环从头到尾遍历字符串A每一位都做同样三件事——算当前被除数、算当前商位、更新余数。所谓逐位除法本质就是竖式除法的循环描述。3.2 循环里只需要三个关键量第一个是当前被除数cur第二个是当前商位第三个是往下一轮传递的余数rem。用伪代码表示就是rem 0 for i in 0..len(a)-1: cur rem * 10 (a[i] - 0) q[i] cur / b rem cur % b这里唯一特殊的地方是第一位计算时rem初始为0。你可以理解成第一次翻页前账本上没有任何遗留。因为B是一位正整数而rem最大只有8所以cur最大也就是8 × 10 9 89cur除以B的结果最大只可能是9。这也是为什么一位数除法根本不需要试商、不需要二分直接整除就完事。整个算法的复杂度是O(n)n是A的位数。1000位的数循环1000次对OJ来说几乎是零负担。但反过来想如果A是10^9位这个算法仍然是线性复杂度一样能跑这就是逐位处理比整体运算高明的地方。3.3 商为什么要用字符数组存有人第一次写这题会把商存成int数组算完再逐个转成字符输出。这样做完全可行但没必要。商的每一位都是0到9的数字直接存成0 商位的字符最后在末尾补一个\0整串就是一个完整的C字符串printf用%s一次就能输出。这里还有个实际好处后面处理前导零的时候字符串只需要移动起始指针不需要复制数组。你在printf里传q startC语言就从start位置开始打印如果用int数组要去掉前缀0就得自己维护偏移量代码会绕很多。当然存成字符数组之后计算时要注意类型转换。a[i] - 0的结果是intcur / b的结果也是int加上0变回char整个过程要心里有数否则很容易写出char类型当int用导致计算错乱的bug。3.4 前导零的问题先留个悬念为什么商的结果里会有前导零因为A的第一位完全可能比B小比如122 ÷ 7第一位1除以7商0。这个0是竖式过程中的合法产物但如果直接输出就变成了017。它不算算法错误却是输出格式错误。这个坑我单独放在后面讲因为它值得拥有自己的章节。4. 可直接提交的C语言代码逐行拆解一遍4.1 完整代码#include stdio.h #include string.h #define MAX 1001 int main() { char a[MAX]; int b; scanf(%s %d, a, b); int len strlen(a); char q[MAX]; int rem 0; int pos 0; for (int i 0; i len; i) { int cur rem * 10 (a[i] - 0); q[pos] cur / b 0; rem cur % b; } q[pos] \0; int start 0; while (start pos - 1 q[start] 0) { start; } printf(%s %d\n, q start, rem); return 0; }4.2 逐段拆解头文件部分stdio.h管输入输出string.h管strlen。MAX定义成1001是因为A最多1000位加上字符串末尾的\0需要1001个字符位置。这个数字不是拍脑袋定的是从题面限制里直接算出来的。scanf那行scanf(%s %d, a, b);。%s会跳过输入开头和中间的空格把第一串数字读进a%d接着读空格后的B。这里要记住%s本身不会读取空格所以不用担心空格混进字符串更不需要额外写getchar去清缓冲区。循环体是整道题的核心。cur rem * 10 (a[i] - 0)q[pos] cur / b 0rem cur % b三行代码完成一位数的除法处理。这里q[pos]是先取q[pos]赋值再把pos加1写起来紧凑但初学者容易看花眼拆成两行也完全没问题效果一样。循环结束后别忘了q[pos] \0。这一步是把商字符串变成合法C字符串的必要操作。如果漏掉printf按%s输出时会一路读到随机内存轻则出现乱码重则段错误。这个坑我在别的题目里踩过代价是一次罚时。4.3 为什么不在循环里直接分段输出有同学会想既然要跳过前导零能不能在循环里判断一下从第一个非零商位开始输出当然能但没必要。分段输出的坏处是每输出一位就得调用一次putcharIO次数变多而且一旦中间逻辑出错调试时你很难分辨是哪一位算错了。先算完整条商再统一去前导零最后一次性printf是最直白也最稳的路线。我看过一些题解把去前导零的过程也塞进循环用flag变量标记是否已经输出过非零位。这种做法在原理上没错但会把循环逻辑和输出逻辑耦合在一起排查问题时多一个变量要盯。考试环境下思路越简单越不容易出错。对我来说循环只负责算商和余数输出格式化单独处理这个边界划分能省掉很多不必要的调试时间。5. 三个NG现场复盘前导零、商为零、读入格式这一章请当排错实录看。如果你能一次AC说明你对边界条件的嗅觉已经很敏锐但大多数人第一次提交都会在下面这些地方翻车。我挨个说清楚当时的症状、排查过程和修复方案。5.1 现场一输出017 3样例能过但测试点红我第一次提交时用的最朴素写法循环算完商直接printf(%s %d, q, rem)。输入样例123456789050987654321 7输出17636684150141093474 3和样例一致我心想这波稳了提交却给我一个WA。当时的排查链路是这样先在本地多测几组数据输入122 7程序输出017 3。手算一下122 ÷ 7商17余3完全没问题但程序输出多了一个前导0。原因在于第一位数字1比除数7小商0是竖式过程中的正常产物但数学上最高位不允许出现0。修复办法就是while循环跳前导零。这里要注意去前导零不能影响商本身就是0的合法情况所以要加start pos - 1这个上界条件。我后来给自己总结了一个口诀前缀0可以删最后一个字符永远不删。5.2 现场二输入1 2商直接消失了去前导零写反的另一个典型是把while条件写成while(q[start] 0) start;没有pos - 1的上界。本地测122 7时一切正常一测1 2就露馅q[0] 0pos 1start会一直往后走走到超出字符串末尾最后printf打印的是空串。在OJ上表现为输出开头一个空格然后才是余数1看起来诡异得很。我复盘时盯着输出看了半天一度以为是空格问题把printf格式改来改去直到把q和start分别打印出来才意识到start已经越界。真正问题出在删除循环的逻辑上删除前缀0时必须保留商字符串的最后一位哪怕这一位恰好就是0。1除以2合法的商就是0这个0必须出场。经过这次教训我深刻体会到边界条件不是靠记的是靠分组测试逼出来的。像我后来做任何除法类题目都会准备几组固定用例大数除大数、小数除大数、大数除1、小数除小数。每组覆盖一种边界全过才敢提交。5.3 现场三scanf和清缓冲区的多余操作第三个坑不是出在算法而是出在输入读取。我见过不少新手包括当时的我看到网上的经验帖说scanf之后要清缓冲区于是写了一个getchar()去吸收空格。结果在本地手测没问题提交到OJ上某些测试点读入错位数据对不上号白白WA好几次。其实C语言的scanf在处理%d和%s时都会自动跳过输入流里的空白字符包括空格、换行、制表符。你根本不需要手动去清什么缓冲区。额外加一个getchar()反而可能把下一个测试点需要读到的字符提前吃掉。尤其是多组测试数据的题目这种错误特别隐蔽。正确的做法就是按官方样例的输入格式来一个%s读A一个%d读B中间留一个空格不多写任何东西。scanf这种老派函数虽然有很多毛病但在这种简单格式下非常可靠别画蛇添足。5.4 三个坑的对照表坑点错误表现根因正确做法商的前导零输出017 3最高位为0也算进了结果用start和指针偏移跳过前缀0商为0的合法输出输出开始有个空格while删过头删掉了唯一一位start pos - 1保证至少留一位读入画蛇添足本地正常OJ错误getchar干扰后续读入直接scanf(%s %d)不加多余操作这三个坑单独看都是小问题但它们共同指向一件事做题时不能只看算法流程对不对还要看输出格式、边界输入、输入读取这些外围细节。PAT的判题器非常严格多一个空格、少一位0都是WA。6. 顺着1017把高精度四则运算一次补齐1017只是高精度运算里最简单的一种除数只有一位连试商都不需要。但把它作为起点把高精度加法、减法、乘法、多位数除法的思路都捋一遍备考性价比很高。我按自己的理解把这一整个套路拆开讲一下。6.1 高精度加法低位对齐满十进一加法的大体思路是把两个大数从低位开始逐位相加每一位都处理进位。为了方便进位通常会把字符串倒序存进数组让个位在数组下标0的位置。这样加出来的进位会自然往数组后部走不用每次把整个数组往后挪。// s1、s2已倒序存储res也是倒序 for (int i 0; i len1 || i len2 || carry; i) { int sum carry; if (i len1) sum s1[i] - 0; if (i len2) sum s2[i] - 0; res[i] sum % 10 0; carry sum / 10; }这个代码的精髓在于循环条件里加了carry进位一旦存在循环就不会提前结束避免了最高位进位露掉的情况。和1017的除法对比一下你会发现处理方式不一样除法是从高位往低位走加法是从低位往高位走。方向不同但逐位处理的底层思想完全一致。6.2 高精度减法借位处理和比较大小减法比加法麻烦一点核心是两件事先比较两个数的大小保证被减数不小于减数然后逐位相减不够就向前一位借1当10。借位处理在代码上的实现比手算更直接因为你不需要真的去找前一位是谁只需要记一个借位标记每一位计算时先减去这个标记。// 先比较大小确保a b否则交换并加负号 int borrow 0; for (int i 0; i len; i) { int diff (a[i] - 0) - borrow; if (i len_b) diff - (b[i] - 0); if (diff 0) { diff 10; borrow 1; } else { borrow 0; } res[i] diff 0; }减法结果同样有前导零问题比如1000减去999结果是0001需要去掉前缀0。这跟1017里商的前导零处理是同一个思路写一次就会了。6.3 高精度乘法逐位相乘再错位累加乘法不需要模拟乘数每一位去乘以被乘数再错位相加的整个过程而是可以直接用双重循环把a[i]和b[j]的乘积累加到res[i j]位置上全部累加完后再统一进位。for (int i 0; i len_a; i) { for (int j 0; j len_b; j) { res[i j] (a[i] - 0) * (b[j] - 0); } } for (int i 0; i len_a len_b; i) { if (res[i] 10) { res[i 1] res[i] / 10; res[i] % 10; } }这段代码进位的时机放在了最后好处是双重循环里只需要做乘法累加逻辑更清晰。坏处是res数组里可能存了比较大的临时值但因为每一位最多是9 × 9 81再加上最多len位累加int完全扛得住不用担心溢出。6.4 多位数除法的思路最终还是回到减法很多同学做完1017下次遇到除数也是大数的题就懵了。一位数除法可以直接整除是因为cur最大只有89商不会超过9多位数除法不行你需要真正去试商。最朴素的实现是用减法在被除数里反复减去除数每减一次商加1。这个做法在除数很小、被除数很大时慢得离谱但思路最直白。更标准的做法是模拟长除法每次从被除数里截出一段和除数比较大小不够就往后再截一位够了就试商并更新余数。试商的过程可以用倍增法加速但PAT乙级对多位数除法考得不算深思路到位就能应付大多数题目。6.5 我自己的刷题顺序建议如果你时间有限先把1017这种一位数除法吃透把字符串数组操作的套路练熟。然后去写高精度加法因为加法最简单能快速建立信心。接着减法再乘法。做完这几个你再看PAT乙级后半程涉及大数的题会明显感觉到字符串处理的底子变厚了。翁恺老师在公开课里反复强调过刷题不要只满足于AC要能讲出自己每行代码为什么这样写。我第一次听这话没啥感觉直到被1017的前导零卡了三遍才真正明白。能AC只说明结果对能把边界情况讲清楚才算真的掌握了。最后分享一点个人习惯。1017这道题我前后提交了5次才算真正过前两次就死在商的前导零上。后来我把高精度四则运算的模板都敲了一遍再回头看待处理这种看起来只是除法的题才发现它其实是整个大数运算的起手式。刷PAT乙级最忌讳AC后立刻翻页——代码过了但中间那个坑不复盘下次换个数照样踩。如果你也在刷这题拿到AC之后建议手动把122 7、1 2、1000 1这三组数据跑一遍能一次输出正确才算把这道题真正拿下了。