lightoj1045

maksyuki 发表于 oj 分类，标签: 基础算法-简单数学

27 8月 2015

1045 - Digits of Factorial

f(0) = 1 f(n) = f(n - 1) * n, if(n > 0)Factorial of an integer is defined by the following function

So, factorial of 5 is 120. But in different bases, the factorial may be different. For example, factorial of 5 in base 8 is 170.

In this problem, you have to find the number of digit(s) of the factorial of an integer in a certain base.

Input

Input starts with an integer T (≤ 50000), denoting the number of test cases.

Each case begins with two integers n (0 ≤ n ≤ 10⁶) and base (2 ≤ base ≤ 1000). Both of these integers will be given in decimal.

Output

For each case of input you have to print the case number and the digit(s) of factorial n in the given base.

Sample Input

Output for Sample Input

55 108 1022 3

1000000 2

0 100

Case 1: 3Case 2: 5Case 3: 45Case 4: 18488885

Case 5: 1

题目类型：简单数学

算法分析：结果是log base n!，直接打表计算出ln i的值(前缀和)，然后对于每一个查询直接计算结果，注意使用cout输出格式可能会出现问题！输出结果要加上EPS！！！！！！

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1e9 + 7;
const int maxn = 1000000 + 66;

double val[maxn+66];

void Solve ()
{
    for (int i = 1; i <= maxn; i++)
        val[i] = val[i-1] + log (i);

}


int main()
{
//    freopen ("aaa.txt", "r", stdin);

    Solve ();

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        printf ("Case %d: ", flag++);
        int n, base;
        scanf ("%d%d", &n, &base);

        printf ("%d\n", (int) (val[n] / log (base) + EPS) + 1);
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1e9 + 7;

const int maxn = 1000000 + 66;

double val[maxn+66];

void Solve ()

{

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

val[i] = val[i-1] + log (i);

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

Solve ();

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

printf ("Case %d: ", flag++);

int n, base;

scanf ("%d%d", &n, &base);

printf ("%d\n", (int) (val[n] / log (base) + EPS) + 1);

}

return 0;

}

lightoj1043

lightoj1054

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

lightoj1045

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论