首页 > 代码库 > hdoj Last non-zero Digit in N! 【数论】

hdoj Last non-zero Digit in N! 【数论】

2024-07-10 18:35:10   222人阅读

找规律！

求N！最后非0位的值。比方2是120的最后一个不是0的值。
输入N比較大，要大数保存。
注意到最后0的个数是与5的因数的个数相等。设f（n）为n！的最后非0位。
那么f(n)=((n%5)!* f(n/5) *2^(n/5))%10
因数2的个数始终大于5，从1開始每连续5个划分为1组，当中5的倍数仅仅提取出一个因数5后，
组成一个新的数列1到n/5，我们有1*2*3*4*5=6*7*8*9*5=2（取最后一个非0位），这里就是2^（n/5）。
再乘上剩下来的几个数字就可以
（比方n是123，那么第一次会剩下121,122,123三个数没有被分配）。

比如：23 就能够变为 f(23) = ((3)! * f(4) * 2^(4))%10; f(4) = 4;

故f(23) = 4； 參考http://blog.csdn.net/yihuikang/article/details/7721875

Last non-zero Digit in N!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5908    Accepted Submission(s): 1471


Problem Description
The expression N!, read as "N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, for example,
N N!
0 1
1 1
2 2
3 6
4 24
5 120
10 3628800

For this problem, you are to write a program that can compute the last non-zero digit of the factorial for N. For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce "2" because 5! = 120, and 2 is the last nonzero digit of 120.
 

Input
Input to the program is a series of nonnegative integers, each on its own line with no other letters, digits or spaces. For each integer N, you should read the value and compute the last nonzero digit of N!.

Output
For each integer input, the program should print exactly one line of output containing the single last non-zero digit of N!.
 

Sample Input
1 
2 
26 
125 
3125 
9999
 

Sample Output
1
2
4
8
2
8
 


 
#include<stdio.h>
#include<string.h>
const int di[4] = { 6, 2, 4, 8};//这是2的次幂最后一位的循环；
const int pre[10] = { 1, 1, 2, 6, 4,2,2,4,2,8};//前十个数的最后一位； 
int a[200], ls;
char s[200];
void tran( int ls )//转换 将个位放在a[0]处 
{
	for( int i =ls-1; i >= 0; i -- )
	a[ls-i-1] = s[i]-'0';
}
void mult(  )
{
	int i, t=0;//t是借位； 
	for( i = ls-1; i >= 0; i -- )
	{
		int q = t*10+a[i];
		a[i] = q/5;
		t = q%5;
	}
	while( ls > 0&&a[ls-1] == 0 ) --ls;//排除后面的0 细致考虑一下
}
int la_no_num( )
{
	if( ls == 1 ) return pre[a[0]]; //假设仅仅有一位直接输出或返回
	int x1 = pre[a[0]%5];   //这是f（n%5）
	mult( );
	int x2 = di[(a[0]+a[1]*10)%4];//这是2^(n/5) 为什么仅仅算前两位（提示：同余定理）
	int ans = (x1*x2*la_no_num())%10;//f(n)=((n%5)!* f(n/5) *2^(n/5))%10
	return ans;
}
int main()
{
	int la, i;
	while( ~scanf( "%s", s ) )
	{
		ls = strlen(s);
		tran(ls);	
		printf( "%d\n", la_no_num() );
	}
	
}



联系
我们