n!在k进制下的后缀0

时间：2021-11-21 23:17:13

问n! 转化成k进制后的位数和尾数的0的个数。【UVA 10061 How many zeros and how many digits?】

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  . . . b − .

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 ( < B ≤ ), which is the base of the number

system you have to consider. As for example ! =  (in decimal) but it is  in hexadecimal number

system. So in Hexadecimal ! 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  − .

Sample Input

Sample Output

#include <stdio.h>

#include <math.h>

int cal_digit(int n, int b)

{

    int i;

    double l;

    for (i = , l = ; i <= n; i++)

        l += log10(i) / log10(b);

    return l + ;

}

int cal_zero(int n, int b)

{

    int i, d, m, t;

    for (i = , d = ; i <= b; i++) {

        m = ;

        while (b % i == ) {

            m++;

            d = i;

            b /= i;

        }

    }

    for (t = ; n > ; ) {

        t += n / d;

        n /= d;

    }

    return t / m;

}

int main(void)

{

    int n, b;

    while (scanf("%d%d", &n, &b) != EOF)

        printf("%d %d\n", cal_zero(n, b), cal_digit(n, b));

    return ;

}

UVA

n! 在k进制下后缀0的个数。【洛谷 一道中档题】

输入输出格式

输入格式：

每组输入仅包含一行：两个整数n，k。

输出格式：

输出一个整数：n!在k进制下后缀0的个数。

输入输出样例

输入样例#1：

10 40

输出样例#1：

2

说明

对于20%的数据，n <= 1000000， k = 10

对于另外20%的数据，n <= 20， k <= 36

对于100%的数据，n <= 10^12，k <= 10^12

　　

给出一个k进制的数n，求n!里一共有多少个0。【ZOJ Factorial Problem in Base K】

https://www.cnblogs.com/linqiuwei/p/3258408.html 【好解释】

先把n转化为10进制下的数。

把n！分解质因数。

把k分解质因数。

求所有的k的质因数中，除以n！的相同质因数中最小的。就是answer。

　　

How many zeros are there in the end of s! if both s and s! are written in base k which is not necessarily to be 10? For general base, the digit order is 0-9,A-Z,a-z(increasingly), for example F4 in base 46 is actually 694 in base 10,and f4 in base 46 is 1890 in base 10.

Input

There are multiple cases(less than 10000). Each case is a line containing two integers s and k(0 ≤ s < 2^63, 2 ≤ k ≤ 62).

Output

For each case, output a single line containing exactly one integer in base 10 indicating the number of zeros in the end of s!.

Sample Input

101 2

12 7

Sample Output

3

1

　　

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define test freopen("test.txt","r",stdin)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

string s;

int n;

const int p[]={,,,,,,,,,,,,,,,,,};

int a[];

int main()

{

    while(cin>>s>>n)

    {

        memset(a,,sizeof(a));

        ll tmp=;

        ll k=;

        for(int i=s.size()-;i>=;i--)

        {

            if(s[i]<=''&&s[i]>='')

                tmp+=(s[i]-'')*k;

            else if(s[i]<='Z'&&s[i]>='A')

                tmp+=(s[i]-'A'+)*k;

            else

                tmp+=(s[i]-'a'+)*k;

            k*=n;

        }

        for(int i=;i<;i++)

        {

            while(n%p[i]==&&n>)

            {

                n/=p[i];

                a[i]++;

            }

        }

        ll ans=(1LL<<)-;

        for(int i=;i<;i++)

        {

            ll now=tmp,tot=;

            while(now>)

            {

                now/=p[i];

                tot+=now;

            }

            if(a[i]>)

                ans=min(ans,tot/a[i]);

        }

        printf("%lld\n",ans);

    }

}

ZOJ

相关文章