被n整除的n位数
题目描述
“被n整除的n位数”是这样定义的：记这个n位数为an...a2a1。首先an不为 0。从an开始从左到右扫描每一位数字，前 1 位数（即an）能被 1 整除，前 2 位数anan−1a_na_{n-1}anan−1能被 2 整除，以此类推…… 即前i位数能被i整除（i=1,⋯,n）。
例如 34285 这个 5 位数，其前 1 位数 3 能被 1 整除；前 2 位数 34 能被 2 整除；前 3 位数 342 能被 3 整除；前 4 位数 3428 能被 4 整除；前 5 位数 34285 能被 5 整除。所以 34285 是能被 5 整除的 5 位数。
本题就请你对任一给定的n，求出给定区间内被n整除的n位数。
友情提示：被偶数整除的数字一定以偶数结尾；被 5 整除的数字一定以 5 或 0 结尾；被 10 整除的数字一定以 0 结尾。
输入格式：
输入在一行中给出 3 个正整数：n（1<n≤15），以及闭区间端点a和b（1≤a≤b<1015）。
输出格式：
按递增序输出区间 [a,b] 内被n整除的n位数，每个数字占一行。
若给定区间内没有解，则输出No Solution。
输入样例 1：
5 34200 34500
输出样例 1：
34200
34205
34240
34245
34280
34285
输入样例 2：
4 1040 1050
输出样例 2：
No Solution
思路分析:
由于nnn的最大值为 15，而区间[a,b][a, b][a,b]的跨度可能高达101510^{15}1015，直接暴力遍历区间内的每一个数字是绝对行不通的（101510^{15}1015次循环即便在超级计算机上也跑不完）。
我们需要换个思路：不是从区间里去找符合条件的数，而是构造出符合条件的数。
一、 核心算法：深度优先搜索
我们可以从左往右，一位一位地确定这个nnn位数。
1. 构造规则
- 第 1 位：从1…91 \dots 91…9中选择一个数字d1d_1d1，判断d1d_1d1是否能被 1 整除（显然成立）。
- 第 2 位：在第一位的基础上，从0…90 \dots 90…9中选择一个数字d2d_2d2，组成新数X2=X1×10+d2X_2 = X_1 \times 10 + d_2X2=X1×10+d2。判断X2X_2X2能否被 2 整除。
- 第iii位：在第i−1i-1i−1位的数Xi−1X_{i-1}Xi−1基础上，选择数字did_idi，组成Xi=Xi−1×10+diX_i = X_{i-1} \times 10 + d_iXi=Xi−1×10+di。判断XiX_iXi能否被iii整除。
- 以此类推，直到第nnn位。
2. 范围剪枝
在构造的过程中，我们可以实时判断当前正在构造的数字前缀是否可能落在[a,b][a, b][a,b]范围内。
- 假设当前已经构造到了第iii位，数值为
current。 - 这个前缀能形成的最小nnn位数是
min_val = current * 10^(n-i)。 - 这个前缀能形成的最大nnn位数是
max_val = current * 10^(n-i) + (10^(n-i) - 1)。
举一个例子来说就是,我们设n=2n=2n=2,当前第一位是1,那么这个前缀最小得到数是101010,最大得到的数是191919
- 剪枝逻辑：如果
max_val < a或者min_val > b，说明当前这个分支无论后面怎么填，都不可能落在[a,b][a, b][a,b]之间，直接回溯（放弃这个分支）。
二、 数值范围考虑
在写这道题时，必须选择正确的数据类型来存储这个nnn位数。
1.int(32位有符号整型)
- 最大值：231−1=2,147,483,6472^{31} - 1 = 2,147,483,647231−1=2,147,483,647。
- 限制：大约到2×1092 \times 10^92×109。
- 结论：如果数字超过10910^9109（即 10 位数），
int就会溢出。本题nnn最大为 15，所以绝对不能用int。
2.long long(64位有符号整型)
- 最大值：263−1=9,223,372,036,854,775,8072^{63} - 1 = 9,223,372,036,854,775,807263−1=9,223,372,036,854,775,807。
- 限制：大约到9×10189 \times 10^{18}9×1018。
- 结论：本题最大是101510^{15}1015，完全在
long long的范围内。
3. 补充：long类型
- 在 32 位系统（或 Windows 64 位）上，
long通常只有 32 位，和int一样。 - 在 Linux 64 位系统上，
long通常是 64 位。 - 建议：为了跨平台稳定，涉及大整数时统一使用
long long。
三、 代码实现
#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;ll n,a,b;boolflag;voiddfs(intindex,ll shu){//结束条件if(index==n&&shu>=a&&shu<=b){printf("%lld\n",shu);flag=true;return;}ll max_shu=shu;ll min_shu=shu;//生成当前数所能到达的最小数和最大数for(inti=0;i<n-index;i++){min_shu*=10;max_shu=max_shu*10+9;}//如果生成的最大数还不够a或者最小的数就已经超过了b,就不用继续往下找数了if(max_shu<a||min_shu>b)return;//枚举下一个数字for(inti=0;i<=9;i++){ll next_shu=shu*10+i;//当前选的这个数字是不是满足条件if(next_shu%(index+1)==0)//添一位数字,看看是不是能被index+1整除dfs(index+1,next_shu);}}intmain(){cin>>n>>a>>b;for(inti=1;i<=9;i++){dfs(1,i);}if(flag==false)cout<<"No Solution"<<endl;}四、 总结
- 虽然符合条件的数并不多，但如果不带范围剪枝，搜索空间依然存在无效分支。带上范围剪枝（即a,ba, ba,b的约束）能让程序在n=15n=15n=15时瞬间出解。
- 进制问题：这道题考察的是十进制下的整除特征。题目中提到的“被偶数整除必以偶数结尾”等提示，可以作为代码中
for循环的微小优化（比如第 2, 4, 6… 位只枚举偶数），但即使不加这些优化，DFS + 范围剪枝也足够快了。 - 大整数类型总结：
- 10910^9109以内：用
int。 - 101810^{18}1018以内：用
long long。 - 超过101910^{19}1019：需要用到
__int128_t（GCC 特有，支持到103810^{38}1038）或者手动实现“大数类”。
- 10910^9109以内：用
解惑其他
有的小伙伴还是有些疑问,会这样认为:
如果每一层都有 10 个分叉，15 层确实是101510^{15}1015，这和暴力枚举没有区别。
但这里的关键在于：整除约束极大地压缩了搜索空间。这不是一棵“茂密”的树，而是一棵被严重修剪过的树。
我们可以从以下几个维度来分析一下：
1. 分叉数并不严格是 10
在每一层，我们并不是盲目地尝试 10 个数字，只有满足current % step == 0的数字才能进入下一层。
让我们看看前几层的实际情况：
- 第 1 层：9 个选择 (1−91-91−9)。
- 第 2 层：要求前两位能被 2 整除。这意味着第 2 位只能是偶数（0, 2, 4, 6, 8）。分叉数降到了 5 个。
- 第 5 层：要求前五位能被 5 整除。这意味着第 5 位只能是 0 或 5。分叉数降到了 2 个。
- 第 10 层：要求前十位能被 10 整除。这意味着第 10 位只能是 0。分叉数降到了 1 个。
- 其他层：比如第 3 层，要在 10 个数字里找能让和被 3 整除的数，平均只有 3 或 4 个。
2. “剪枝”举例？
假设你构造的前 3 位是341。
341不能被 3 整除 (3+4+1=83+4+1=83+4+1=8)。- 在 DFS 中：程序在第 3 层就直接
return了。 - 这意味着什么？：这意味着以
341开头的所有数字（从341,000,000,000,000到341,999,999,999,999共1 兆（101210^{12}1012）个数）被这一行代码一瞬间全部排除了。
这就是为什么它比暴力枚举快的原因。
题目还给了一个区间[a,b][a, b][a,b]。我们在代码中加入的：
if(max_possible<a||min_possible>b)return;这又是一次巨大的修剪。
如果你正在构造342...，而区间的最小值aaa是500...。
DFS 发现当前路径能产生的最大值也比aaa小，就会直接剪掉这个分支。
实际上:
对于n=14n=14n=14，只有 1132 个这样的数。
程序实际运行时的循环次数可能只有几万次，这在现代 CPU 上。1s足够了
该同学理解的“深度”没错，但高估了“宽度”。整除性约束就像一把锋利的剪刀，把那棵拥有101510^{15}1015个叶子的巨树剪得只剩下几根细长的树枝。