L2-056 被n整除的n位数 - java

L2-056 被n整除的n位数

---

语言	时间限制	内存限制	代码长度限制	栈限制
Java (javac)	400 ms	512 MB	16KB	8192 KB
Python (python3)	400 ms	256 MB	16KB	8192 KB
其他编译器	400 ms	64 MB	16KB	8192 KB

---

题目描述：

“被 $n$ 整除的 $n$ 位数”是这样定义的：记这个 $n$ 位数为 $a_n\cdots a_2{a}_1$ 。首先 $a_n$ 不为 0。从 $a_n$ 开始从左到右扫描每一位数字，前 $1$ 位数（即 $a_n$）能被 $1$ 整除，前 $2$ 位数 $a_n{a}_{n-1}$ 能被 2 整除，以此类推…… 即前 i 位数能被 $i$ 整除$（i=1,\cdots ,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\le 15）$，以及闭区间端点 $a$ 和 $b（1\le a\le b<10^{15}）$。

输出格式：
按递增序输出区间 $[a,b]$ 内被 $n$ 整除的 $n$ 位数，每个数字占一行。

若给定区间内没有解，则输出 No Solution。

输入样例 1：

5 34200 34500

输出样例 1：

34200
34205
34240
34245
34280
34285

输入样例 2：

4 1040 1050

输出样例 2：

No Solution

---

输出$a\sim b$ 之间所有满足前 $i$ 位数能被 $i$ 整除的数。

---

emmmmmmm

搜索

从最高位开始依次找到前$i$位能被$i$整除的数，直到填满$n$位为止。

由于给定的$a,b$可能是一个差距极大值，所以需要先替换为$n$位数的最大最小值。即 $a=10^{n-1},b=10^n-1$。

---

import java.io.*;
import java.util.*;public class Main
{static long n, a, b;static boolean flag = true;// x:当前的数// dep:当前填入的位数static void dfs(long x, int dep){// 填满n位if (dep == n){// 在指定范围内if (a <= x && x <= b){flag = false;out.println(x);}return;}// 依次判断0~9的数是否满足条件for (int i = 0; i <= 9; i ++){// 将当前数插入long res = x * 10 + i;// 判断前i位是否为i的倍数if (res % (dep + 1) == 0) dfs(res, dep + 1);}}public static void main(String[] args) throws IOException{n = sc.nextInt();a = sc.nextLong();b = sc.nextLong();// n位数的最小值long min = (long) (Math.pow(10, n - 1));// 替换a和b的范围a = Math.max(a, min);b = Math.min(b, min * 10 - 1);// 从最高位开始查找，用一个固定值来简化搜索for (long i = a / min; i <= b / min; i ++)dfs(i, 1);if (flag) out.println("No Solution");out.flush();out.close();}static Scanner sc = new Scanner(System.in);static PrintWriter out = new PrintWriter(System.out);}

---

dfs
dfs

---

如果有说错的 或者 不懂的 尽管提 嘻嘻

一起进步！！！

---

闪现