UVAOJ10061 | 哈喽哈咯

Written by razrlele 22:21 December 6, 2014

UVAOJ10061

有一点意思的数论题, 求N!在B进制数系统下的结果的位数以及末尾的零的个数.

求位数比较简单, 因为M位的B进制数最大值为B^M-1, 故

B^M-1 < N! <= B^(M+1)-1,

进而推出

B^M <= N! < B^(M+1)

求N!结果的位数就首先得把N!分解成不大于B的素数的乘积, 然后不断地从这些素数中提取素数使其积等于B, 直到不能提取出来为止, 成功提取的次数就是末尾0的个数.

* File Name: uvaoj10061.cpp

* Author: razrLeLe

* Mail: razrlele@outlook.com

* Homepage: https://yueyu.io

* Created Time: 2014年12月05日星期五 18时06分11秒

#define LOCAL

#include "vector"

#include "set"

#include "deque"

#include "queue"

#include "algorithm"

#include "functional"

#include "iostream"

#include "cstdio"

#include "cmath"

#include "cstdlib"

#include "string"

#include "cstring"

#include "string.h"

#include "map"

#include "cctype"

using namespace std;

#define INF 0x3f3f3f3f

int primenum[1000];

int N, B;

void calculate_zero()

{

memset(primenum, 0, sizeof(primenum));

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

{

int tmpi = i;

for(int j = 2; j <= B && j <= tmpi; j++)

{

while(tmpi%j == 0)

{

primenum[j]++;

tmpi /= j;

}

int count = 0;

while(1)

{

int tmp = B;

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

{

if(!tmp) break;

while(tmp %i == 0 && primenum[i])

{

tmp /= i;

primenum[i]--;

}

if(tmp == 1)

count++;

else

break;

}

printf("%d ", count);

return ;

}

void calculate_num()

{

double lognum = 0;

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

lognum += log(i);

int bitnum = (floor)(lognum/log(B) + 1e-9)+1;

// 这个地方有可能出现2.999999999的情况故得加个1e-9消除误差

printf("%d\n", bitnum);

return ;

}

int main()

{

#ifdef LOCAL

freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/out.txt", "w", stdout);

#endif

while(cin >> N >> B)

{

calculate_zero();

calculate_num();

}

return 0;

}