放牧代码和思想
专注自然语言处理、机器学习算法
    正处于一个非常忙的阶段,抱歉不会经常回应任何联络

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),否则乘以2a-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//////////////////////////////////
14047162 hankcs 1150 Accepted 148K 0MS C++ 1762B 2015-04-04 14:58:05

Reference

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

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

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机