POJ 1150 The Last Non-zero Digit 题解《挑战程序设计竞赛》

POJ 1150 The Last Non-zero Digit

超大组合数：求超大组合数P(n, m)的最后一个非零位。

4.1更加复杂的数学问题 

模运算的世界 

今天过节，管它什么节，对我来说都一样，来刷一题渲染一下节日气氛。

终于刷到【登峰造极——高级篇】了，我却一点登峰造极的感觉都没有

P(n, m)=n! / (n-m)!，问题归结于求n!的最后一个非零位。

先把n!中所有的10因子去掉，问题归结于求最后一位。但是10不是质因数，不好处理，退而求其次，将所有的2^a*5^b去掉，得到一个新数列f(1)…f(n)，也即定义：

f(n) := n除以2^a*5^b，a和b分别是质因子2和5的个数

如果计算出了f(1)…f(n)中以3,7,9结尾的数的个数，就可以求出它们乘积的最后一位。因为3,7,9的n次方的最后一位是以4为周期的（其实2也是），这样就不用做很多乘法，也避免了溢出问题。至于怎么求，其实是一个递归的过程。并不先将2^a*5^b除掉，直接讨论n!，将其分为奇偶两个部分，比如 1 2 3 4 5 6-> 2 4 6| 1 3 5。而2 4 6可以进行除2^a这个操作，所以除2直到得到奇数数列，问题归结于奇数数列。

对奇数数列1 3 5 7 9 11 13 15 17 19，每10个单位跨度都有一个379，所以有n / 10 + (如果个位数大于379则加一)个，另外其中还可能有5的倍数，于是还需要除5递归。

得到f(1)*…*f(n)的最后一位后，还需要针对a和b进行讨论，如果a<b，也就是5的系数大，那么结果肯定是5（奇数*5的个位一定是5），否则乘以2^a-b进行修正。这时候，又可以利用“2的n次方的最后一位是以4为周期”这个性质减少运算了。

#include<iostream>  
#include<cstring>  
#include<cstdio>  
using namespace std;

// 数n!的质因子x的个数
int fact_prime(int n, int x)
{
	int res = 0;
	while (n)
	{
		res += n / x;
		n /= x;
	}
	return res;
}

// 定义 f(n) := n除以2^a*5^b，a和b分别是质因子2和5的个数
// f(1)...f(n)中以x(1 3 7 9)结尾的奇数的个数
int odd_end_with(int n, int x)
{
	if (n == 0) return 0;
	return n / 10					// 1.a 每10个数都有一个
		+ (n % 10 >= x)				// 1.b n的个位数可能产生一个
		+ odd_end_with(n / 5, x);	// 2.  迭代除以5，以满足5^b这个条件
}

// f(1)...f(n)中以x(1 3 7 9)结尾的数的个数
int end_with(int n, int x)
{
	if (n == 0) return 0;
	return end_with(n / 2, x)		// 1. 数列中的偶数，迭代以满足除以2^a这个条件
		 + odd_end_with(n, x);		// 2. 数列中的奇数
}


int table[4][4] = 
{
	6, 2, 4, 8,//2^4 2 2^2 2^3 的最后一位
	1, 3, 9, 7,//同理3
	1, 7, 9, 3,//同理7  
	1, 9, 1, 9,//同理9  
};

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n, m;
	while (~scanf("%d%d", &n, &m))
	{
		m = n - m;
		int two	= fact_prime(n, 2) - fact_prime(m, 2);
		int five	= fact_prime(n, 5) - fact_prime(m, 5);
		int three	= end_with(n, 3) - end_with(m, 3);
		int seven	= end_with(n, 7) - end_with(m, 7);
		int nine	= end_with(n, 9) - end_with(m, 9);
		if (two < five)
		{
			puts("5");
			continue;
		}
		int res = 1;
		if (two > five) res *= table[0][(two - five) % 4];
		res *= table[1][three % 4];
		res *= table[2][seven % 4];
		res *= table[3][nine  % 4];
		res %= 10;
		printf("%d\n", res);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

Reference

http://bbezxcy.iteye.com/blog/2164453

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1150 The Last Non-zero Digit 题解《挑战程序设计竞赛》