POJ 1150 The Last Non-zero Digit 阶乘最后非0位

2024-04-23 19:58
文章标签 non poj 阶乘 last zero 1150 digit

本文主要是介绍POJ 1150 The Last Non-zero Digit 阶乘最后非0位,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

转自:http://www.cppblog.com/abilitytao/archive/2009/10/31/99907.html

这个题怎么来做呢?先别急,我们先来讨论一下下面几个子问题:
1.如何求出n阶乘中质因数x(比如说5)出现的次数?
比如说15的阶乘 :1*2*3*4*5*6*7*8*9*10*11*12*13*14*15
由于5这个质因数只在5的倍数里面才出现,所以我从5,10,15中各抽出一个5,这相当于有15/5个质因数5,之后5,10,15就变成了1,2,3;
由于非5的倍数显然不在考虑范围之内,所以我们只需继续讨论它的子问题3!即可。
这样,我们可以用递归来解决这个问题。有了这个方法,我们是不是能够轻易地解决n!末尾有多少个0呢?想想看...n!后0的个数是不是就和某个质因数的个数有关呢?^_^
比如说,我们要求5出现的次数,可以这样写:

int get5( int n) // 计算n!中质因子5的出现次数
{
    if(n==0)
        return 0;
    return n/5+get5(n/5);
}


 2.如何求出n!阶乘最后非0位?
比如说我们要找10!最后非0位,由于质因数2和5组合之后会使得末尾产生0.那么我们不妨把10!中2,5质因数全部去掉,(但是请注意2的数目其实比5的要多,所以我们要在最后考虑多余的2对末位的影响)
如 1*2*3*4*5*6*7*8*9*10 去掉2 ,5 因子后 就是1*1*3*1*1*3*7*1*9*1,由于2,5因子已经被去除,那么剩下的数字末尾一定是3,7,9,1中四者之一。然后我们再求出这么一串数相乘以后末尾的数是几.最后再补上2对末位的影响即可!

总结一下,求10!最后一个非0位的步骤如下:
step1:首先将10!中所有2,5因子去掉;
step2:然后求出剩下的一串数字相乘后末尾的那个数。
step3:由于去掉的2比5多,最后还要考虑多余的那部分2对结果的影响。
step4:output your answer!

正如上面文章里所说的“To compute the number of 3,7,9 among ( f(1) mod 10), ( f(2) mod 10), ..., ( f(N) mod 10) is not so easy”,这里面步骤2是个难点。如何求出剩下的这串数字相乘后最后一位是几呢?这可以转化成求出这些数里面末尾是3,7,9的数字出现的次数(为啥?因为这些数的n次方是有规律的,周期为4,不信你可以推一下)
好,现在问题就是如何求出这串数字中末尾3,7,9各自出现的次数了;

一个数列实际上可以分成偶数列和奇数列,以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中的个数也就是1 2 3 4 5中的个数,也就是说我们又把这个问题划分成了一个原来问题的子问题。

f(n) = f(n/2) + g(n),g(n)表示奇数列中的数目,所以我们需要解决g(n)

再次观察g(n)

实际上又分成了两部分1 3 7 9 11 13 17 19 21。。。以及5的奇倍数5,15,25。。。说明又出现了子问题,如果要统计这个数列中末尾为x(1,3,7,9)的个数可以这样写:g(n,x) = n/10+(n%10 >= x)+g(n/5,x) 

这样利用了两个递归方程,我们就可以在lgn的时间内计算出末尾为1,3,7,9的数的个数了

好了,现在我们得到了这串数字中末尾是3,7,9的数字的个数,我们利用循环节的性质可以快速地算出这串数字相乘后mod 10的结果,在考虑下当时多除的2(其实也可以用循环节来处理),便可求出答案!




解决了上面两个子问题,我想求P(n,m)最后一个非0位就变得十分容易了。
P(n,m)实际上等于 n! / (n-m)!
我们可以求出n! 和(n-m)!中质因数2,5,3,7,9分别出现的次数,然后再各自相减。
然后再用循环节处理,即可!
BTW,这里还要注意一个trick,就是2的出现次数如果小于5,(这对于排列数来说是可能的)我们可以直接输出5,如果2的数目等于5,那么2的循环节不需要考虑。至于3,7,9的循环节,由于这些数的4次方末位刚好是1,所以就不需要特殊考虑了。


#include<cstdio>int get2 ( int n )
{if ( n == 0 )return 0;return n/2 + get2(n/2);
}int get5 ( int n )
{if ( n == 0 )return 0;return n/5 + get5(n/5);
}int g ( int n, int x )
{if ( n == 0 )return 0;return n/10 + ( n%10 >= x ) + g(n/5,x);
}int getx ( int n, int x )
{if ( n == 0 )return 0;return getx ( n/2, x ) + g ( n, x );
}int table[4][4] =
{6,2,4,8, // 2的循环节。2^0 = 1,需要特殊处理。1,3,9,7, // 31,7,9,3, // 71,9,1,9,  // 9
};int main()
{int n, m;while ( scanf("%d%d",&n,&m) != EOF ){int num2 = get2(n) - get2(n-m);int num5 = get5(n) - get5(n-m);int num3 = getx(n,3) - getx(n-m,3);int num7 = getx(n,7) - getx(n-m,7);int num9 = getx(n,9) - getx(n-m,9);int res = 1;if ( num5 > num2 ){printf("5\n");continue;}else{if ( num5 != num2 ){res *= table[0][(num2-num5)%4];res %= 10;}res *= table[1][num3%4];res %= 10;res *= table[2][num7%4];res %= 10;res *= table[3][num9%4];res %= 10;}printf("%d\n",res);}return 0;
}


这篇关于POJ 1150 The Last Non-zero Digit 阶乘最后非0位的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/929735

相关文章

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i