1.8　逐位整除数

逐位整除数是一类精妙有趣的整数。

定义n位逐位整除数：从高位开始，高1位能被1整除（显然），高2位能被2整除，高3位能被3整除，……，以此类推，直至整个n位数能被n整除。

例如，102456就是一个6位逐位整除数，因102456能被6整除，高5位即10245能被5整除，高4位即1024能被4整除，高3位即102能被3整除，高2位即10能被2整除。

【问题1】　以6位逐位整除数102456为前缀的12位逐位整除数有多少个？

【思考】　从第7位开始，向高位逐位续位。

所谓逐位续位，就是根据“逐位整除”的定义依次确定第7位数字，再确定第8，9，…位，直到第12位止。

由1024560%7＝5（即1024560除7余5），第7位可取2或9，可确保7位数被7整除。

（1）第7位数字取2续位。

由10245620%8＝4，第8位只能取4，才能确保8位数被8整除；

由102456240%9＝6，第9位只能取3，才能确保9位数被9整除。

要确保10位数被10整除，第10位数字只能取0；

由10245624300%11＝10，第11位只能取1，才能确保11位数被11整除；

由102456243010%12＝10，第12位只能取2，才能确保12位数被12整除。

由此，确定第7位数字取2时，可得12位逐位整除数102456243012。

（2）第7位数字取9续位。

由10245690%8＝2，第8位只能取6，才能确保8位数被8整除；

由102456960%9＝6，第9位只能取3，才能确保9位数被9整除。

要确保10位数被10整除，第10位数字只能取0；

由10245696300%11＝4，第11位只能取7，才能确保11位数被11整除；

由102456963070%12＝10，第12位只能取2，才能确保12位数被12整除。

由此，确定第7位数字取9时，可得12位逐位整除数102456963072。

（3）综上得到，以102456为前缀的12位逐位整除数有两个：102456243012，102456963072。

【问题2】　前缀为102456的逐位整除数最多有多少位？

【探求】　以前面两个12位逐位整除数为基础，从第13位开始，向高位逐位续位。

前缀为102456的12位逐位整除数有以上两个，从这两个数出发逐位续位，探求能最多续到哪一位。

（1）从102456243012开始续位。

由1024562430120%13＝8，第13位只能取5，即1024562430125为13位逐位整除数；

由10245624301250%14＝2，第14位取0~9，都不能被14整除。

从102456243012开始续位，最多为13位，即1024562430125。

（2）从102456963072开始续位。

由1024569630720%13＝12，第13位只能取1，即1024569630721为13位逐位整除数；

由10245696307210%14＝0，第14位只能取0，即10245696307210为14位逐位整除数；

由102456963072100%15＝10，第15位只能取5，即102456963072105为15位逐位整除数；

由1024569630721050%16＝10，第16位只能取6，即1024569630721056为16位逐位整除数；

由10245696307210560%17＝7，第17取0~9，都不能被17整除，到上面16位止步。

从102456963072开始续位，最多为16位，即1024569630721056。

（3）综上可得，前缀为102456的逐位整除数最多为16位，即1024569630721056。

通过以上求解，以102456为前缀的12位逐位整除数有两个，不带任何前缀的12位逐位整除数有多少个？

同时，以102456为前缀的逐位整除数最多达16位，不带任何前缀的逐位整除数最多有多少位？

这些，应用程序设计解决是适宜的。

【拓展】　存在n位逐位整除数的整数n是否有最大值？

对于指定的正整数n，搜索共有多少个不同的n位逐位整除数。在此基础上探索，存在n位逐位整除数的整数n是否有最大值。

试探索指定的n位逐位整除数，且限制指定的第e位只能取指定数字f，输出所有满足限位要求的n位逐位整除数。

1. 递推设计要点

根据逐位整除数的递推特性，也可以应用递推设计求解逐位整除数。

注意到逐位整除数的构造特点：n位逐位整除数的高n-1位是一个n-1位逐位整除数。因而可在每一个n-1位逐位整除数后加一个数字j（0~9），得到一个n位数。测试该n位数如果能被n整除，则得到一个n位逐位整除数。

递推基础为n＝1位，显然有g＝9个一位数j（1~9）。

注意到逐位整除数的位数可能比较大，为了递推方便，设置两个二维数组：

a（i，d）为k-1位的第i个逐位整除数的从高位开始第d（1~n-1）位数字。

b（m，d）为递推得到k位的第m个逐位整除数的从高位开始第d（1~n）位数字。

完成从k-1位推出k位之后，需把m赋值给g，把b数组赋值给a数组，为下一步递推作准备。

最后输出递推得到的n位逐位整除数的个数g及所有n位逐位整除数。

如果e＞0，即有限位要求，只有当第e位数字为数字f即满足条件a[i][e]＝＝f时才输出限位解，并用变量s统计限位解的个数。

当递增至n位没有得到n位逐位整除数时（g＝0），输出“无解！”后结束。

2. 递推程序设计

3. 程序运行示例与说明

事实上，不带限位条件的24位逐位整除数有3个，而增添了限位，则只有上述两个满足限位“第6位为数字2”的要求。

也可以不带限位运行程序，运行结果如下所示。

这就是不带限位搜索25位的输出，得唯一的一个25位逐位整除数，实际上就是在以上面第一个24位逐位整除数后加上一个数字5而成，而其他24位逐位整除数后加上任意一个数字后所得25位数都不能被25整除。

运行程序，输入n＝26，显示“无解！”。也就是说，在唯一25位逐位整除数后加上任意一个数字后所得26位数都不能被26整除，因而得知逐位整除数的最多位数是25。

注意到本案例n不可能大于25，在此范围内以上设计能快速求得相应的解。

变通：修改程序，求解n位逐位整除数的个数f（n）的最大值。