老师在群里发的题，就发了提干，不知道名字我就自己给它命名吧。
题干：从某数的最后一位开始数，这个数是几位就能被几整除，
然后依次从这个数最后一位开始删除数字，然后剩下的n-1位数字可以被（n-1）整除，
比如10245就满足条件，10245能被5整除，1024能被4整除，102能被3整除。。。。，
任意输入n，求所有满足条件的数，并探求n的最大值
几行代码就基本解决了，吓我一跳，小小得意，这么6，hhhh。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public class 数 {
static int[] data=new int[50];
static boolean fal=false;
public static void main(String[] args) {
long t1=System.nanoTime();
dfs(0,1);
long t2=System.nanoTime();
System.out.println(t2-t1+"纳秒");
}
private static void dfs(long num,int k) {
if(fal)return;
if(k==19){
System.out.println(num);
fal=true;
return;
}
for (int j = 9; j >= 0; j--) {
if((num*10+j)%k==0){
dfs(num*10+j,k+1);
}
}
}
}
|
当时用long到达18位后结果就溢出了，所以没推出n最长是多少。其实当时知道换成BigInteger就可以解决
只是当时不知道BigInteger有直接取模的函数，以为蛮难的，其实不然。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| import java.math.BigInteger;
public class 数 {
static int[] data=new int[50];
static boolean fal=false;
public static void main(String[] args) {
long t1=System.nanoTime();
BigInteger num=BigInteger.ZERO;
for (int i = 1; i < 30; i++) {
dfs(num,1,i);
data=new int[50];
fal=false;
}
long t2=System.nanoTime();
System.out.println(t2-t1+"纳秒");
}
private static void dfs(BigInteger num,int k,int l) {
if(fal)return;
if(k>l){
System.out.println(l+":"+num);
fal=true;
return;
}
for (int j = 9; j >= 0; j--) {
BigInteger t=(num.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(j)));
if(t.mod(BigInteger.valueOf(k)).toString().equals("0")){//(num*10+j)%k==0)
dfs(t,k+1,l);//dfs(num*10+j,k+1)
}
}
}
}
|
运行结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| 1:9
2:98
3:987
4:9876
5:98765
6:987654
7:9876545
8:98765456
9:987654564
10:9876545640
11:98765456405
12:987606963096
13:9876069630960
14:98760696309604
15:987606963096045
16:9876062430364208
17:98485872309636009
18:984450645096105672
19:9812523240364656789
20:96685896604836004260
21:966858966048360042609
22:9668589660483600426096
23:72645656402410567240820
24:402852168072900828009216
25:3608528850368400786036725
26:0
27:0
28:0
29:0
783320379纳秒
|