~~~
# Big Number
Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 31542????Accepted Submission(s): 14684
~~~
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
一開始看見這道題目不是很明白到底是什么意思,搞了好久才明白是:給一個數規定輸入數字的個數,案例中給出了2也就是輸入2個數,輸入的這兩個數求它的階乘的位數,一開始想著是這樣做:直接求指出然后求長度,這是最不需要動腦子的方法,但是,這個方法并不奏效,因為階乘的數值是很大的,普通的int,long類型一旦求比較大的數的階乘的時候往往會溢出,所以最好的方法應該是避免求他的值才行。
斯特林公式就可以用于求這個階乘的位數,斯特林公式(Stirling's approximation)是一條用來取n的階乘的近似值的數學公式。一般來說,當n很大的時候,n階乘的計算量十分大,所以斯特林公式十分好用,而且,即使在n很小的時候,斯特林公式的取值已經十分準確。
上式兩邊同時取log10,得到的是log10(n!) = log10(2*pi*n)/2+n*log10(n/e)所以其位數應該可以表示為: log10(2*pi*n)/2+n*log10(n/e)+1
~~~
~~~~
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
int[] nums = new int[num];
int num_digit = 0;
double d = 1;
int i = 0;
while(i < num)
{
num_digit = scanner.nextInt();
if(num_digit >= 2)
{
d = Math.log10(2 * Math.PI * num_digit) / 2 + num_digit * Math.log10(num_digit / Math.E) + 1;
}
nums[i] = (int)d;
i++;
}
//System.out.println("=====");
for(i = 0 ; i < num; i++)
{
System.out.println(nums[i]);
}
}
}
~~~
另外其他的方法還有
位數= log10(1) + log10(2) + log10(3) + ...... + log10(n) 取整數部分后+1
- 前言
- 求和的問題ACM
- A+B問題acm
- 1091ACM求和
- 杭電ACM1092求和問題詳解
- ACM杭電的1093求和問題
- 杭電ACM1094計算A+B的問題
- 杭電ACM1095解決A+B問題
- 杭電ACM1096求和問題
- 杭電Acm1001解決求和的問題
- 杭電ACM1008電梯問題C++
- 杭電ACM大賽2000關于ASCII碼排序的問題
- 杭電ACM2006奇數的乘積
- 杭電ACM數值統計2008
- 杭電ACM1019求最大公約數
- 杭電ACM1108求最小公倍數
- 杭電ACM2035人見人愛的A^B
- 杭電ACM1061N^N求最右邊的數的問題
- 杭電ACM1021裴波納挈數AGAIN
- 杭電ACm1005求f(n)非遞歸
- 杭電ACM1071The area---------求積分面積
- 杭電ACM吃糖果問題
- 杭電ACm求數列的和2009
- 杭電ACM多項式求和--》2011
- 杭電ACM。。。sort
- 杭電ACM1004
- 杭電ACM2043密碼的問題已經AC
- 杭電ACM2041樓梯問題
- 動態規劃C++::杭電ACM1003
- 杭電ACM----2018母牛的故事
- 杭電ACM2007平方和與立方和
- 盧卡斯隊列
- 全國軟件2. 三人年齡
- 全國軟件3. 考察團組成
- 全國軟件--微生物增殖
- 全國軟件填寫算式
- 全國軟件-----------猜生日
- 全國軟件---------歐拉與雞蛋
- Java經典算法四十例編程詳解+程序實例
- 杭電ACMA + B Problem II問題解析
- 杭電ACM1018BigNumber解析
- 杭電ACM1088 Write a simple HTML Browser Java
- 杭電ACM1106排序Java代碼
- 杭電ACM 1012 u Calculate e java
- 杭電ACM 1020 Encoding java解析
- 杭電1047 An Easy Task - java 解讀
- 杭電ACM 1040 As Easy As A+B java 解讀
- 杭電ACM 1041 Computer Transformation java代碼詳解AC
- 杭電ACM 1030 Delta-wave java代碼解析