第一题是考思路吧,既然只关心power(A,B)的后三位P,那实际上P的值与power(substr(A, length(A)-2), B)的后三位P\'的值是一样的
为便于书写,我们记P(n)为n的后三位数字,不足三位的按实际走
则有P(power(A,B+1))=P(power(A,B)*A)=P(power(P(A), B)*P(A))=P(power(P(A), B))*P(A)
故而只需要考察2~999之间的数字即可,至于B,是否真的需要考察1~9999的范围,得计算后再说
————————————————————————————————————————————————————————————————
先看看A=2时的情况
select p, count(*), max(rn), min(rn) from(select substr(A, length(A)-2) p, rn from (select power(2, rownum) a, rownum rnfrom dual connect by rownum1
order by 4
/
P
COUNT(*)MAX(RN)MIN(RN)
---------------------------------------- ---------- ---------- ----------
128
2107
7
256
2108
8
512
2109
9
024
2110 10
048
2111 11
096
2112 12
192
2113 13
384
2114 14
768
2115 15
536
2116 16
072
2117 17
144
2118 18
288
2119 19
576
2120 20
152
2121 21
304
2122 22
608
2123 23
216
2124 24
432
2125 25
864
2126 26
728
2127 27
P
COUNT(*)MAX(RN)MIN(RN)
---------------------------------------- ---------- ---------- ----------
456
2128 28
912
2129 29
824
2130 30
24 rows selected.
单独观察一下100~109次幂的情况
select substr(A, length(A)-2) p, rn from (select power(2, rownum+99) a, rownum+99 rnfrom dual connect by rownum<=10)
P
RN
---------------------------------------- ----------
376
100
752
101
504
102
008
103
016
104
032
105
064
106
128
107
256
108
512
109
10 rows selected.
可以发现从103开始,已经出现回归的现象了,所不同的是,P(2^3)=8,而P(2^103)=008
当处理到107次幂时,后三位数128已经不存在前导0了,于是就和7次幂的结果128重合了,在此处出现了“回归”
于是容易推出,从207次幂开始,又将再次“回归”
————————————————————————————————————————————————————————————————
回到题目本身,上面这一大段其实都可以不用去看不用去分析,面试的时候哪儿有可能给你工具去做这么大量的计算,所以,对于楼主的问题,我会这么回应:
A的B次幂的后三位数(是1~999之间的一个或一组数字。对于A=1,则P总是1,对于A为10的整数倍的,最多从3次幂开始,P就都是000。) |