首页 > 代码库 > (hdu step 2.3.3)Big Number(求N!的位数)

(hdu step 2.3.3)Big Number(求N!的位数)

2024-11-27 01:29:39   203人阅读

在写题解之前给自己打一下广告哈~技术分享。。抱歉了，希望大家多多支持我在CSDN的视频课程，地址如下：

http://edu.csdn.net/course/detail/209


题目：

Big Number

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 951 Accepted Submission(s): 640
 
Problem Description
In many applications very large integers numbers are required. Some of these applications are using keys for secure transmission of data, encryption, etc. In this problem you are given a number, you have to determine the number of digits in the factorial of the number.
 
Input
Input consists of several lines of integer numbers. The first line contains an integer n, which is the number of cases to be tested, followed by n lines, one integer 1 ≤ n ≤ 107 on each line.
 
Output

            The output contains the number of digits in the factorial of the integers appearing in the input.
 
Sample Input
2
10
20
 
Sample Output
7
19
 
 
Source
Asia 2002, Dhaka (Bengal)
 
Recommend
JGShining


题目大意：

这个题的意思是：给你一个数，让你求出N！由多少位数构成，比如输出10，它的阶乖是3628800 由7位数构成，这时你要输出7；


题目分析：

             这道题对于C/C++的写法来说，n太大阶乘出来的结果已经超出了所能表示的整数的范围。这时候主要有以下两种思考：

1）用科学计数法a*10^n来表示N!。那么这时候n+1就是N！的位数。(其实这种想法就是直接暴力，只不过是在暴力之前做了以下处理。因为N！的范围太大，C/C++的整数范围内存不下)

N的阶乖的位数等于LOG10（N！）＝LOG10（1）＋.....LOG10（N）；


2）用斯特林公式获得N！的近似值。然后计算这个近似值的位数。


需要注意的是：

用第一种方法同样是暴力，他只不过使用对数来处理一下数字太大的问题。既然这样的话，那么是不是使用java来直接求N!就行了呢？我试了一下，是会TLE的。因为java会比C/C++慢3倍以上。而这道题的时间却没有同等程度的放宽。

代码如下：

/*
 * c.cpp
 *
 *  Created on: 2015年2月3日
 *      Author: Administrator
 */


#include <iostream>
#include <cstdio>
#include <cmath>


using namespace std;

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		int i;
		double ans = 0;
		for(i = 1 ; i <= n ; ++i){
			ans += log10(i);
		}

		printf("%d\n",(int)ceil(ans));//ceil()函数用于向上取整.
	}


	return 0;
}






(hdu step 2.3.3)Big Number(求N!的位数)


联系
我们