PKU Judge Online 1423 Big Number

■1423 Big Number

□Problem
n!は10進数表記で何桁になるか求めよ．

□Solution
ある自然数mが10進数表記でd(m)桁になるとき，
d(m)=[log₁₀(m)]+1
が成り立つ．
よって，
d(n!)
=[log₁₀(n!)]+1
=[Σ_k=[1,n]log₁₀(k)]+1

d(n!)を1≦n≦10⁷について予め求めておく．

□Code

view plainprint?

1. package p1423;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     void run(){  
11.         int n=(int)1e7;  
12.         int[] d=new int[n+1];  
13.         double a=0.0;  
14.         for(int i=1; i<=n; i++){  
15.             a+=Math.log10(i);  
16.             d[i]=(int)a+1;  
17.         }  
18.         for(int t=sc.nextInt(); t>0; t--){  
19.             int k=sc.nextInt();  
20.             println(d[k]+"");  
21.         }  
22.     }  
23.   
24.     void println(String s){  
25.         System.out.println(s);  
26.     }  
27.   
28.     void print(String s){  
29.         System.out.print(s);  
30.     }  
31.   
32.     public static void main(String[] args){  
33.         new Main().run();  
34.     }  
35. }  

package p1423;

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{
    Scanner sc=new Scanner(System.in);

    void run(){
        int n=(int)1e7;
        int[] d=new int[n+1];
        double a=0.0;
        for(int i=1; i<=n; i++){
            a+=Math.log10(i);
            d[i]=(int)a+1;
        }
        for(int t=sc.nextInt(); t>0; t--){
            int k=sc.nextInt();
            println(d[k]+"");
        }
    }

    void println(String s){
        System.out.println(s);
    }

    void print(String s){
        System.out.print(s);
    }

    public static void main(String[] args){
        new Main().run();
    }
}