51Nod-1057-N의 등급

N을 입력하여 N의 계승에 대한 정확한 값을 구하십시오.Input 입력 N(1 <= N <= 10000)Output 출력 N의 곱하기 Input 예시 5 Output 예시 120
이 문제를 만난 것도 나의 운이다. 왜냐하면 이전에 이런 고정밀도 문제를 이렇게 할 수 있다는 생각을 전혀 하지 않았기 때문이다. 너무 신기하다. 먼저 나의 원래 방법을 보내라.

#include <stdio.h>
#include <string.h>
#define _MAX 6
#define MAX_ 10000000
int product[MAX_];
int pro[MAX_], num[_MAX];
int rank = 1;

// 
void Carrying(int tag,int i,int j,int *p)
{
    p[i+j]+=tag;
    if (i + j + 1 > rank || (i + j + 1 == rank && p[i + j] > 9))
    {
        rank++;
    }
    if (p[i+j]>9)
    {
        tag=p[i+j]/10;
        p[i+j] %=10;
        Carrying(tag, i+1, j, p);                                // Carrying(tag, i, j+1, p); ， i+j 
    }
    return ;
}

// 
void multiplication(int N)
{
    int i=0,j=0,numLen,productLen,tag;
    for (i = 0; N > 0; i++)
    {
        num[i] = N % 10;
        N /= 10;
    }
    numLen = i;
    productLen = rank;
    for (i = 0; i < productLen; i++)
    {
        pro[i] = product[i];
    }
    memset(product, 0, sizeof(int) * MAX_);

    // 
    for (i=0; i<productLen; i++)
    {
        for (j=0; j<numLen; j++)
        {
            tag= pro[i] *  num[j];
            Carrying(tag, i, j, product);                          // 
        }
    }
    return ;
}

int main()
{
    int N, i = 2, j;
    scanf("%d", &N);
    memset(product, 0, sizeof(int) * MAX_);                    // product 0
    product[0] = 1;
    for (; i <= N; i++)
    {
        multiplication(i);
    }
    // 
    for (j = rank - 1; j >= 0; j--)
    {
        printf("%d",product[j]);
    }
    printf("
");
}

이런 방법은 비교적 자질구레하다. 그래서 이 문제의 테스트 데이터에서 5분의 2의 테스트 데이터만 지나고 나머지는 전부 시간을 초과했다. 그래서 나는 다른 더 간단한 방법을 찾아야 했다. 그래서 아래의 이 교묘한 방법을 만났다.

#include <stdio.h>
#define _MAX 100000000
int main()
{
    int n, i, j, m;
    long long a[10000], c;
    scanf("%d",&n);

    m = 0;
    a[0] = 1;
    for(i = 1; i <= n; i++)
    {
        c = 0;
        for(j = 0; j <= m; j++)
        {
            a[j] = a[j] * i + c;
            c = a[j] / _MAX;
            a[j] %= _MAX;
        }
        if(c > 0)
        {
            m++;
            a[m] = c;
        }
    }
    printf("%lld", a[m]);
    for(i = m - 1; i >= 0; i--)
        printf("%0.8lld", a[i]);
    printf("
");
    return 0;
}

여기서 우리는 만약에 간단하게 곱셈으로 곱셈을 하면 그다지 크지 않아도 데이터 범위가 폭발한다는 것을 알고 있다. 그래서 이 문제의 이 해법은 교묘하게 이 슈퍼 큰 수를 구분했다. 구체적으로 얼마나 넓게 잘라서 개인의 취미를 볼 수 있는지 몇 개의 숫자 유형으로 담을 수 있으면 된다. 여기서 우리는 8개의 너비로 나누어 여덟 명씩 저장하고 마지막으로 포맷 출력을 한다.데이터 폭발 범위의 문제를 교묘하게 피했다.코드를 보면서 이해하는 것은 어렵지 않다. c는 진위와 관련이 있고 m는 절단된 단수와 관련이 있다. 이렇게 해서 모두가 이해할 수 있다고 믿는다. 만약 이해할 수 없다면 돌아가서 수학을 배워라, 착한 Y(^_^)Y!!!