凯发ag旗舰厅登录网址下载
收集整理的这篇文章主要介绍了
poj1150
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
这道题告诉我们递推一定要慢慢细细的推
pmn=n!/m!，我们可以先考虑n!的最后一位是什么
首先最后一位非0位我们首先想到把0都干掉
也就是先把2和5提出来，这两个其实是同样的方法
对于n！中有多少个因数2 f(n)=f(n div 2） n div 2这个不难想
提出2和5之后剩下来的数我们只要考虑末位，只可能是1,3,7,9
当我们讨论末位为x时，设f(n,x)表示n!中提出2和5后某位是x的个数
首先一个数列实际上可以分成偶数列和奇数列，以1*2*3*4*5*6*7*8*9*10为例
分成1 3 5 7 9, 2 4 6 8 10
这样我们尝试分别进行统计，可以发现，实际上2 4 6 8 10中把2提出来就是 1 2 3 4 5 又回到了对n!这种问题
所以不难得到f(n,x) = f(n/2,x) g(n,x),g(n)表示奇数列中的数目，所以我们需要解决g(n)
观察奇数列，实际上又分成了两部分非5的倍数以及5的奇倍数
根据上面处理的经验不难得到 g(n,x) = n/10 (n >= x) g(n/5,x)
这样对于n!的最末非0位就处理出来了
而对于n!/m!,我们只要求出m~n之间的2和5的个数，某位为1,3,7,9的个数
这显然可以用前缀合德思想搞，但要注意2和5的个数谁多谁少
1 const table:
array[
1..
4,
0..
3]
of longint=((
6,
2,
4,
8),
2 (
1,
3,
9,
7),
3 (
1,
7,
9,
3),
4 (
1,
9,
1,
9));
5 var a:
array[
0..
5]
of longint;
6 f,i,n,m,ans:longint;
7
8 function get2(x:longint):longint;
9 begin
10 if x=
0 then exit(
0)
11 else exit(x shr
1 get2(x shr
1));
12 end;
13
14 function get5(x:longint):longint;
15 begin
16 if x=
0 then exit(
0)
17 else exit(x
div 5 get5(x
div 5));
18 end;
19
20 function getx(n,x:longint):longint;
21 begin
22 if n=
0 then exit(
0)
23 else
24 if n
mod 10>=x
then exit(
1 n
div 10 getx(n
div 5,x))
25 else exit(n
div 10 getx(n
div 5,x));
26 end;
27
28 function get(n,x:longint):longint;
29 begin
30 if n=
0 then exit(
0)
31 else exit(get(n shr
1,x)
getx(n,x));
32 end;
33
34 begin
35 while not eof
do
36 begin
37 readln(n,m);
38 m:=n-
m;
39 a[
1]:=get2(n)-
get2(m);
40 f:=get5(n)-
get5(m);
41 if a[
1]
then
42 begin
43 writeln(5);
44 continue;
45 end;
46 ans:=1;
47 a[2]:=get(n,3)-get(m,3);
48 a[3]:=get(n,7)-get(m,7);
49 a[4]:=get(n,9)-get(m,9);
50 if a[1]<>f then
51 ans:=ans*table[1,(a[1]-f) mod 4] mod 10;
52 for i:=2 to 4 do
53 ans:=ans*table[i,a[i] mod 4] mod 10;
54 writeln(ans);
55 end;
56 end. view code
转载于:https://www.cnblogs.com/phile/p/4473120.html
总结
以上是凯发ag旗舰厅登录网址下载为你收集整理的poj1150的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得凯发ag旗舰厅登录网址下载网站内容还不错，欢迎将凯发ag旗舰厅登录网址下载推荐给好友。
