POJ 1150（数论） 代码量极少的解法

先考虑N!最后一位非0的数的求法。

我们构造一个数组table[4]={6,2,4,8}，这个数组的特点就是table[(i+1)%4]=(table[i]*2)%10

那么

table[i]*2相当于是数组下标往右移动了一位（移动到最右边就从左边循环），

table[i]*1  不变

table[i]*2  右1位

table[i]*3  右3位

table[i]*4  右2位

table[i]*5  左1位

table[i]*6  不变

table[i]*7  右1位

table[i]*8  右3位

table[i]*9  右2位

我们发现1,2,3,4，和6,7,8,9效果是一样的，5就是左移一位

因此我们这样求解

1.求得N!之中尾数是1,2,3,4,6,7,8,9所有的数的乘积，保留它在table中需要移动的步数x

2.在其余数中一定是5*1,5*2,5*3,5*4……，我们提取公因式5，求得所有的5的乘积，保留它在table中需要移动的步数y

3.剩下的就是1*2*3*4*5*6……*N/5了，将N除以5，重复1，直到N为0为止，将所有的x和y累加起来

初始化，位置为0，即table[0]=6，1！特殊处理

那么N!/(N-M)!就可以转化为求N!移动的步数，减去(N-M)!移动的步数即可

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define MOD 4

int table[4]={2,4,8,6};

int get(int x)
{
	int ret=0;
	while(x)
	{
		ret=(ret+x/5)%MOD;
		int re=0;
		if(x%5==2)re=1;
		if(x%5==4)re=2;
		ret=(ret+re)%MOD;
		x/=5;
	}
	return ret;
}

int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n<=1||m==0)
		{
			printf("1\n");continue;
		}
		else printf("%d\n",table[(3+get(n)-get(n-m))%MOD]);
	}
	return 0;
}

POJ 1150（数论） 代码量极少的解法,布布扣,bubuko.com

POJ 1150（数论） 代码量极少的解法

原文：http://blog.csdn.net/swust_wbh/article/details/24237225