Informatics Orsay Ibn YBT 1172: find the factorial of n within 10000 | 1.6 14: find the factorial of n within 10000

【 Topic link 】

ybt 1172： seek 10000 within n The factorial
OpenJudge NOI 1.6 14: seek 10000 within n The factorial

【 Topic test site 】

1. High precision

Investigate ： High precision multiplication and low precision
Explanation of high-precision calculation

【 Their thinking 】

First find the largest digit of the result , That is to say $10000!$ Number of digits .
A positive integer is known x The number of digits of is n, So there are ：$n=\lfloor lgx\rfloor +1$（$lgx$: With 10 Bottom x The logarithmic ）
Bits are $\lfloor lg10000!\rfloor +1\le \lfloor lg10000^{10000}\rfloor +1=\lfloor 10000\cdot lg10000\rfloor +1=\lfloor 10000\ast 4\rfloor +1=40001$
The length of the number array is 40005 that will do .
Because of the demand for 10000 The factorial , The number multiplied each time is less than or equal to 10000 The number of , Is a low precision number . The result of factorial is a high-precision number . So we should use high precision times low precision . If you use high precision times high precision , The complexity of the algorithm will increase , It may time out .

【 Solution code 】

solution 1： Use functions and arrays

#include <bits/stdc++.h>
using namespace std;
#define N 40005
void setLen(int a[], int i)
{
    
    while(a[i] == 0 && i > 1)// Remove the superfluous 0
        i--;
    a[0] = i;
}
void Multiply(int a[], int b)//a *= b  High precision multiplication and low precision 
{
    
    int c = 0, i;
    for(i = 1; i <= a[0]; ++i)
    {
    
        a[i] = a[i]*b + c;
        c = a[i] / 10;
        a[i] %= 10; 
    }
    while(c > 0)
    {
    
        a[i] = c % 10;
        c /= 10;
        i++;
    }
    setLen(a, i);
}
void toNum(char s[], int a[])
{
    
    a[0] = strlen(s);
    for(int i = 1; i <= a[0]; ++i)
        a[i] = s[a[0] - i] - '0';
}
void showNum(int a[])
{
    
	for(int i = a[0];i >= 1;--i)
		cout << a[i];
}
int main()
{
    
    int a[N] = {
    1, 1}, n;// High precision number a The initial value is 1 
    cin >> n;
    for(int i = 1; i <= n; ++i)
        Multiply(a, i);
    showNum(a);
    return 0;
}

solution 2： Overloaded operator in class

#include <bits/stdc++.h>
using namespace std;
#define N 40005
struct HPN
{
    
    int a[N];// Array of numbers 
    HPN()
    {
    
        memset(a, 0, sizeof(a));
    }
    HPN(char s[])
    {
    
        memset(a, 0, sizeof(a));
        int len = strlen(s);
        for(int i = 0; i < len; ++i)
            a[len - i] = s[i] - '0';
        a[0] = len;
    }
    void setLen(int i)
    {
    
        while(a[i] == 0 && i > 1)// Remove the superfluous 0
            i--;
        a[0] = i;
    }
    void operator *= (int b)//a *= b  High precision multiplication and low precision 
    {
    
        int c = 0, i;
        for(i = 1; i <= a[0]; ++i)
        {
    
            a[i] = a[i]*b + c;
            c = a[i] / 10;
            a[i] %= 10; 
        }
        while(c > 0)
        {
    
            a[i] = c % 10;
            c /= 10;
            i++;
        }
        setLen(i);
    }
    void show()
    {
    
        for(int i = a[0]; i >= 1; --i)
            cout << a[i];
    }
};
int main()
{
    
    HPN a("1");// High precision digital a The initial value is 1 
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        a *= i;// High precision multiplication and low precision 
    a.show();
    return 0;
}