题解：P4973 毒瘤之神奇进制

· · 题解

前置知识

\log_a(b) = {\log(b) \over \log(a)} \log(ab) = \log(a) + \log(b) \log_c(ab) = \log_c(a) + \log_c(b) len = \log_{10}(n) + 1

题意

为了方便书写，这里的 s_i 为题目给出的数的第 i 位。

题意可简化为求以下式子的值：

\log_{10}(\prod_{i = 0}^{n-1} a^i \cdot \prod_{i = 1}^n s_i)+1

Solution

\log_{10}(\prod_{i = 0}^{n-1} a^i \cdot \prod_{i = 1}^n s_i)+1 = \log_{10}(a^{\sum_{i = 0}^{n-1} i} \cdot \prod_{i = 1}^n s_i)+1 = \log_{10}(a^{n(n-1) \over2} \cdot \prod_{i = 1}^n s_i)+1 = \log_{10}(a^{n(n-1) \over2}) + \log_{10}(\prod_{i = 0}^n s_i)+1 = \log_{10}(a^{n(n-1) \over2}) + \sum_{i = 1} ^n \log_{10} s_i +1 = {\log(a^{n(n-1) \over2}) \over \log (10)} + \sum_{i = 0} ^n \log_{10} s_i +1 = {\log(a^{n(n-1) \over2}) \over \log (10) \cdot \log(a)} \cdot \log(a) + \sum_{i = 1} ^n \log_{10} s_i +1 = {(n-1)n \cdot \log(a) \over 2\log (10)} + \sum_{i = 1} ^n \log_{10} s_i +1 = {(n-1)n \over 2} \cdot \log_{10} a + \sum_{i = 1} ^n \log_{10} s_i +1

Code

#include<cstdio>
#include<cmath>
#include<cstring>
const int N = 1e5+5;
char S[N];
#define ll long long
inline void Solve(void){
    int a;
    std::scanf("%d",&a);
    std::scanf("%s",S+1);
    int n = std::strlen(S+1);
    long double ans = 0;
    for(int i = 1;i<=n;++i) ans += std::log10(S[i]-'0');
    ans += 1.0 * n * std::log10(a) / 2 * (n-1);
    ll len = std::floor(ans) + 1ll;
    std::printf("%lld\n",len);
}
int main(){
    int T;
    std::scanf("%d",&T);
    while(T--) Solve();
    return 0;
}