刷刷刷

数学刷刷刷

1.Digits of Factorial

题意大体是给一个(1e6)大小的(n)然后问其(n!)的(k)进制位数。

我感觉遇到阶乘，虽然不是经验主义，但是求位数大致应该是和(log_{10})有关的，所以我们先设所求答案为(x)，那么显然可得$$n!<=k^{x}$$然后很显然，(n!)必然无法处理，那么又很显然，这两端都是许多个数相乘，重点在于他们相乘的数量多，那么我么们等式两边同时取(log_{10})得

[lg n!<=lg k^{x} ]

[lg1 + lg2+lg3+···+lg n <= x imes lg k ]

[frac{(lg1 + lg2+···+lg n)}{lg k}<=x ]

解得(x)

代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 9;
double sum[N];
int main() 
{
    ll a, b, L;
    int cas = 0;
    int t;
    cin >> t;
    for (int i = 1; i <= 1e6; i++) {
        sum[i] = sum[i-1] + log(i);
    }
    while (t--) {
        int n;cin >> n;
        int base;cin >> base;
        cout << "Case " << ++cas << ": ";
        if (n == 0)cout << 1 << endl;
        else {
            cout << (int)(sum[n]/log(base)) + 1 << endl;
        }
    }
}