1.8　逐位整除數(shù)

逐位整除數(shù)是一類精妙有趣的整數(shù)。

定義n位逐位整除數(shù)：從高位開始，高1位能被1整除（顯然），高2位能被2整除，高3位能被3整除，……，以此類推，直至整個(gè)n位數(shù)能被n整除。

例如，102456就是一個(gè)6位逐位整除數(shù)，因102456能被6整除，高5位即10245能被5整除，高4位即1024能被4整除，高3位即102能被3整除，高2位即10能被2整除。

【問題1】　以6位逐位整除數(shù)102456為前綴的12位逐位整除數(shù)有多少個(gè)？

【思考】　從第7位開始，向高位逐位續(xù)位。

所謂逐位續(xù)位，就是根據(jù)“逐位整除”的定義依次確定第7位數(shù)字，再確定第8，9，…位，直到第12位止。

由1024560%7＝5（即1024560除7余5），第7位可取2或9，可確保7位數(shù)被7整除。

（1）第7位數(shù)字取2續(xù)位。

由10245620%8＝4，第8位只能取4，才能確保8位數(shù)被8整除；

由102456240%9＝6，第9位只能取3，才能確保9位數(shù)被9整除。

要確保10位數(shù)被10整除，第10位數(shù)字只能取0；

由10245624300%11＝10，第11位只能取1，才能確保11位數(shù)被11整除；

由102456243010%12＝10，第12位只能取2，才能確保12位數(shù)被12整除。

由此，確定第7位數(shù)字取2時(shí)，可得12位逐位整除數(shù)102456243012。

（2）第7位數(shù)字取9續(xù)位。

由10245690%8＝2，第8位只能取6，才能確保8位數(shù)被8整除；

由102456960%9＝6，第9位只能取3，才能確保9位數(shù)被9整除。

要確保10位數(shù)被10整除，第10位數(shù)字只能取0；

由10245696300%11＝4，第11位只能取7，才能確保11位數(shù)被11整除；

由102456963070%12＝10，第12位只能取2，才能確保12位數(shù)被12整除。

由此，確定第7位數(shù)字取9時(shí)，可得12位逐位整除數(shù)102456963072。

（3）綜上得到，以102456為前綴的12位逐位整除數(shù)有兩個(gè)：102456243012，102456963072。

【問題2】　前綴為102456的逐位整除數(shù)最多有多少位？

【探求】　以前面兩個(gè)12位逐位整除數(shù)為基礎(chǔ)，從第13位開始，向高位逐位續(xù)位。

前綴為102456的12位逐位整除數(shù)有以上兩個(gè)，從這兩個(gè)數(shù)出發(fā)逐位續(xù)位，探求能最多續(xù)到哪一位。

（1）從102456243012開始續(xù)位。

由1024562430120%13＝8，第13位只能取5，即1024562430125為13位逐位整除數(shù)；

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

從102456243012開始續(xù)位，最多為13位，即1024562430125。

（2）從102456963072開始續(xù)位。

由1024569630720%13＝12，第13位只能取1，即1024569630721為13位逐位整除數(shù)；

由10245696307210%14＝0，第14位只能取0，即10245696307210為14位逐位整除數(shù)；

由102456963072100%15＝10，第15位只能取5，即102456963072105為15位逐位整除數(shù)；

由1024569630721050%16＝10，第16位只能取6，即1024569630721056為16位逐位整除數(shù)；

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

從102456963072開始續(xù)位，最多為16位，即1024569630721056。

（3）綜上可得，前綴為102456的逐位整除數(shù)最多為16位，即1024569630721056。

通過以上求解，以102456為前綴的12位逐位整除數(shù)有兩個(gè)，不帶任何前綴的12位逐位整除數(shù)有多少個(gè)？

同時(shí)，以102456為前綴的逐位整除數(shù)最多達(dá)16位，不帶任何前綴的逐位整除數(shù)最多有多少位？

這些，應(yīng)用程序設(shè)計(jì)解決是適宜的。

【拓展】　存在n位逐位整除數(shù)的整數(shù)n是否有最大值？

對(duì)于指定的正整數(shù)n，搜索共有多少個(gè)不同的n位逐位整除數(shù)。在此基礎(chǔ)上探索，存在n位逐位整除數(shù)的整數(shù)n是否有最大值。

試探索指定的n位逐位整除數(shù)，且限制指定的第e位只能取指定數(shù)字f，輸出所有滿足限位要求的n位逐位整除數(shù)。

1. 遞推設(shè)計(jì)要點(diǎn)

根據(jù)逐位整除數(shù)的遞推特性，也可以應(yīng)用遞推設(shè)計(jì)求解逐位整除數(shù)。

注意到逐位整除數(shù)的構(gòu)造特點(diǎn)：n位逐位整除數(shù)的高n-1位是一個(gè)n-1位逐位整除數(shù)。因而可在每一個(gè)n-1位逐位整除數(shù)后加一個(gè)數(shù)字j（0~9），得到一個(gè)n位數(shù)。測試該n位數(shù)如果能被n整除，則得到一個(gè)n位逐位整除數(shù)。

遞推基礎(chǔ)為n＝1位，顯然有g(shù)＝9個(gè)一位數(shù)j（1~9）。

注意到逐位整除數(shù)的位數(shù)可能比較大，為了遞推方便，設(shè)置兩個(gè)二維數(shù)組：

a（i，d）為k-1位的第i個(gè)逐位整除數(shù)的從高位開始第d（1~n-1）位數(shù)字。

b（m，d）為遞推得到k位的第m個(gè)逐位整除數(shù)的從高位開始第d（1~n）位數(shù)字。

完成從k-1位推出k位之后，需把m賦值給g，把b數(shù)組賦值給a數(shù)組，為下一步遞推作準(zhǔn)備。

最后輸出遞推得到的n位逐位整除數(shù)的個(gè)數(shù)g及所有n位逐位整除數(shù)。

如果e＞0，即有限位要求，只有當(dāng)?shù)趀位數(shù)字為數(shù)字f即滿足條件a[i][e]＝＝f時(shí)才輸出限位解，并用變量s統(tǒng)計(jì)限位解的個(gè)數(shù)。

當(dāng)遞增至n位沒有得到n位逐位整除數(shù)時(shí)（g＝0），輸出“無解！”后結(jié)束。

2. 遞推程序設(shè)計(jì)

3. 程序運(yùn)行示例與說明

事實(shí)上，不帶限位條件的24位逐位整除數(shù)有3個(gè)，而增添了限位，則只有上述兩個(gè)滿足限位“第6位為數(shù)字2”的要求。

也可以不帶限位運(yùn)行程序，運(yùn)行結(jié)果如下所示。

這就是不帶限位搜索25位的輸出，得唯一的一個(gè)25位逐位整除數(shù)，實(shí)際上就是在以上面第一個(gè)24位逐位整除數(shù)后加上一個(gè)數(shù)字5而成，而其他24位逐位整除數(shù)后加上任意一個(gè)數(shù)字后所得25位數(shù)都不能被25整除。

運(yùn)行程序，輸入n＝26，顯示“無解！”。也就是說，在唯一25位逐位整除數(shù)后加上任意一個(gè)數(shù)字后所得26位數(shù)都不能被26整除，因而得知逐位整除數(shù)的最多位數(shù)是25。

注意到本案例n不可能大于25，在此范圍內(nèi)以上設(shè)計(jì)能快速求得相應(yīng)的解。

變通：修改程序，求解n位逐位整除數(shù)的個(gè)數(shù)f（n）的最大值。