hdu1018

//hdu1018
//Big Number
//題意:計算階乘的位數
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 1e7 + 7;
int num[MAXN];
const double PI = 3.1415926;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    int n;
    while(T--){
        cin >> n;
        //Case 1
        // 任意一個正整數num的位數等于(int)log10(num) + 1
        // 推導:假設 10^(x - 1) <= num < 10^x，那麼顯然num的位數為x位
        // 取對數後得到：x - 1 <= log10(num) < x
        // 向下取整後得 log10(num) = x - 1，或向上取整後得log10(num) + 1 = x
        // 故 x = log10(num) - 1
        // 即num的位數為log10(num) - 1
        // 現假設 sum = 1 * 2 * 3 * … * n = n!
        // 則sum的位數為 (int)log10(sum) + 1 = (int)log10(1 * 2 * 3 * … * n) + 1
        //                              = (int)log10(1) + (int)log10(2) + … + (int)log10(n) + 1
        // 現在就算n取到1e7，都能很快求得其階乘的位數
        double ans = 0;
        for(int i = 1; i <= n; i++)
            ans += log10(i);
        cout << (int)ans + 1 << endl;//進1法，隻要有小數部分就舍去加1
        
        //Case 2
        // 0ms
        //斯特林公式
        //斯特林公式（Stirling's approximation）是一條用來取n的階乘的近似值的數學公式。一般來說，當n很大的時候，n階乘的計算量十分大，是以斯特林公式十分好用，而且，即使在n很小的時候，斯特林公式的取值已經十分準确。
        // n! ≈ sqrt(2πn) * (n/e)^n
        //而log10(n!)就可求出n!的位數,
        // log10(n!) = log10((n/e)^n * sqrt(2πn))
        //           = log10(n/e)^n) + log10(sqrt(2πn)
        //           = nlog10(n) - nlog10(e) + 0.5 * log10(2πn)
        //           = nlog10(n) - n(log(e)/log(10)) + 0.5 * log10(2πn)
        //           = nlog10(n) - n/log(10) + 0.5 * log10(2πn)
        /*
        cout << (int)(n * log10(n) - n / log(10) + 0.5 * log10(2 * PI * n)) + 1 << endl;
        */
        /*
        //Case 3:過不了的正确算法
        // MLE
        //數組實作求大數階乘及其位數，但若n取到1e7,其階乘位數已達65657060位，非常大,而且記憶體很大，都有幾百兆
        memset(num, 0, sizeof(num));
        int digit = 1;
        num[0] = 1;
        for(int i = 2; i <= n; i++){
            int carry = 0;//進位标志
            for(int j = 0; j < digit; j++){
                int tmp = num[j] * i + carry;
                num[j] = tmp % 10;
                carry = tmp / 10;
                if(j == digit - 1 && carry)
                    digit++;
            }
        }
        for(int i = digit - 1; i >= 0; i--)
            cout << num[i];
        cout << endl;
        cout << digit << endl;
        */
    }
}