Uva 10061 进制问题【公式推导】

刺骨的言语ヽ痛彻心扉 2023-07-04 06:18 5阅读 0赞

**Discription**  
Given a decimal integer number you will have to find out how many trailing zeros will be there in its  
factorial in a given number system and also you will have to find how many digits will its factorial have  
in a given number system? You can assume that for a b based number system there are b different  
symbols to denote values ranging from 0 . . . b − 1.

**Input**  
There will be several lines of input. Each line makes a block. Each line will contain a decimal number  
N (a 20bit unsigned number) and a decimal number B (1 < B ≤ 800), which is the base of the number  
system you have to consider. As for example 5! = 120 (in decimal) but it is 78 in hexadecimal number  
system. So in Hexadecimal 5! has no trailing zeros.

**Output**  
For each line of input output in a single line how many trailing zeros will the factorial of that number  
have in the given number system and also how many digits will the factorial of that number have in  
that given number system. Separate these two numbers with a single space. You can be sure that the  
number of trailing zeros or the number of digits will not be greater than 231 − 1.

**Sample Input**  
2 10  
5 16  
5 10

**Sample Output**  
0 1  
0 2  
1 3

**题意**  
给定一个十进制整数N和一个十进制整数b。  
求N！在b禁止下末尾0的个数，并且求出N！在b进制下一共有多少位。

**思路**

*  求位数  
    以10进制为例：

lg10=1
     lg100=2
     lg1000=3
     ......

并且：

lgN=0(n<10)
    lgN=1(10<=N<=99)
    lgN=2(100<=N<=999)
    ......

所以我们容易推断:  
 N ! 的 位 数 = f l o o r ( l o g b N ! ) + 1 N!的位数=floor(log\_bN!)+1 N!的位数=floor(logbN!)\+1

因为N！运算太大容易爆：  
所以对阶乘化简：  
 l o g b n ! = l o g b 1 + l o g b 2 + . . . + l o g b n log\_bn!=log\_b1+log\_b2+...+log\_bn logbn!=logb1\+logb2\+...\+logbn

*  末尾0的个数  
    讲N!转化成b进制末尾0的个数，即求因数b被N整除的最高次数。  
    假设讲b写成

b=b1^k11*b12^k12*...*bi^k1i*..*bn^k1n
       =(b1^c11*b2^c12*...*bi^c1i*...*bn^c1n)^t1
     N!=A*(b1^k21*b2^k22*...*bi^k2i*...*bn^k2n)
       =(b1^c21*b2^c22*...*bi^c2i*...*bn^c2n)^t2

所以0的个数就是k21/k11,k22/k12,…,k2n/k1n中的最小值。

**AC代码**

#include <bits/stdc++.h>
    using namespace std;
    int d[1100],m[1100];
    
    int cal(int n,int b)
    { 
        memset(d,0,sizeof(d));
        memset(m,0,sizeof(m));
        int cnt=1,ans=0x7fffffff;
        for(int i=2; i<=b; i++)
        { 
            while(b%i==0)
            { 
                d[cnt]=i;
                while(b%i==0)
                { 
                    m[cnt]++;
                    b/=i;
                }
                cnt++;
            }
        }
        for(int i=1; i<cnt; i++)
        { 
            int t=0;
            int p=n;
            while(p)
            { 
                t+=p/d[i];
                p/=d[i];
            }
            ans=min(ans,t/m[i]);
        }
        return ans;
    }
    
    int main()
    { 
        int n,b;
        while(scanf("%d%d",&n,&b)!=EOF)
        { 
            double l=0;
            for(int i=2; i<=n; i++)
                l+= log10(i)/log10(b);
            l++;
            int de = floor(l);
            int z = cal(n,b);
            printf("%d %d\n",z,de);
        }
        return 0;
    }