UVa 10856 - Recover Factorial

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

給你 N ，找出某數的階層 M! ，質因數分解後得到總共的質因數個數 = N ，求 M 的最小值。

Solution

一開始用 dp[n] = dp[n-1] + x ，x 為 n 的質因數個數，不過速度太慢了XD。

利用 DP 先將單獨數字的質因數個數算出: factorial[i*j] = factorial[i] + factorial[j]
再計算階乘所需的: factorial[i] += factorial[i - 1] ，從 i = 2 開始往上做:

$$\begin{aligned} &2! = 2\\\\ &3! = 2! \times 3\\\\ &4! = 3! \times 4\\\\ &\cdots \end{aligned}$$

最後再用 Binary search 找出 n 所對應的階層。

Code

UVa 10856UVa 10856 - Recover Factorial

#include<cstdio>
#include<algorithm>
#define N 2703664

int factorial[N];

void solve();
int binary_search(int n);//找第一個等於 n 的，如沒有回傳 -1
int main()
{
    solve();

    int n, Case = 1;

    while (scanf("%d", &n) && n >= 0)
    {
        printf("Case %d: ", Case++);
        if (!n)
            puts("0!");
        else
        {
            int ans = binary_search(n);
            if (ans == -1)
                puts("Not possible.");
            else
                printf("%d!\n", ans);
        }
    }
    return 0;
}
void solve()
{
    std::fill(factorial, factorial + N, 1);
    factorial[0] = factorial[1] = 0;

    // 對 i (非階乘)做質因數分解後所需的質數個數
    for (int i = 2; i < N; i++)
    {
        if (factorial[i] == 1)//如不是質數，在前面就已經做過了
            for (int j = 2; j*i < N; j++)
                factorial[i*j] = factorial[i] + factorial[j];
    }

    //i! 所需的質數個數 
    for (int i = 2; i < N; i++)
        factorial[i] += factorial[i - 1];
}
int binary_search(int n)
{
    int left = 0, right = N - 1, mid = (left + right) / 2;
    while (left < right)
    {
        if (n <= factorial[mid])
            right = mid;
        else
            left = mid + 1;

        mid = (left + right) / 2;
    }

    return factorial[mid] == n ? mid : -1;
}