用了高精,50分求助

P1009 [NOIP1998 普及组] 阶乘之和

OrangeRED @ 2024-07-24 18:25:25

#include<bits/stdc++.h>
using namespace std;

int a[2000],b[2000],c[4000];

string time(string x,string y){//高精乘 
    int lenx = x.size(),leny = y.size();
    for(int i=0;i<lenx;i++) a[i+1] = x[lenx-i-1] - '0';//字符to数字 
    for(int i=0;i<leny;i++) b[i+1] = y[leny-i-1] - '0';//并且倒序 
    for(int i=1;i<=lenx;i++){//开始运算 
        for(int j=1;j<=leny;j++){
            c[i+j-1] += a[i]*b[j];
            c[i+j] += c[i+j-1]/10;
            c[i+j-1] %= 10;
        }
    }
    int maxl = lenx+leny;
    while(!c[maxl] && maxl!=1) maxl--;//去除前导0 
    string sss="";
    for(int i=maxl;i>=1;i--) sss+=char(c[i]+'0');//逐位拼接 
    return sss;
}

string sum(string m,string n){//高精加(结构基本同上) 
    int lenm = m.size(),lenn = n.size();
    for(int i=0;i<lenm;i++) a[i+1] = m[lenm-i-1] - '0';
    for(int i=0;i<lenn;i++) b[i+1] = n[lenn-i-1] - '0';
    int maxl = max(lenm,lenn);
    for(int i=1;i<=maxl;i++){
        c[i] += a[i]+b[i];
        c[i+1] += c[i]/10;
        c[i] %= 10;
    }
    if(c[maxl+1]) maxl++;
    while(!c[maxl] && maxl!=1) maxl--;
    string sss="";
    for(int i=maxl;i>=1;i--) sss+=char(c[i]+'0');
    return sss;
}

int main(){
    int n;cin>>n;
    string s;
    string ans = "1",suma = "0";//初始化 
    for(int i=1;i<=n;i++){//阶乘 
        s = char(i+'0');
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        ans = time(ans,s);//阶乘累加
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        suma = sum(suma,ans);//加入答案
    }
    cout<<suma;
    return 0;
}

by __1943 @ 2024-07-24 18:41:54

#include<iostream>
#include<cstring>
using namespace std;
int n,a[90],b[90],c[90],f[90],d=0,len_a,len_b=1,len_c=1,len_ans,m=1;
string s;
int main(){
    cin>>n;
    b[0]=1; //初始化
    for(int i=1;i<=n;i++){ //计算i的阶乘,已经算好了i-1的阶乘
        len_a=0; //i的长度
        int p=i;
        while(p>0){ //把i存进a数组
            a[len_a++]=p%10;
            p/=10;
        }
        for(int j=0;j<len_a;j++) //计算a*b(i*(i-1)的阶乘),即i的阶乘,看不懂的网上查,我也不知道为什么
            for(int k=0;k<=len_b;k++)
                c[j+k]+=a[j]*b[k];
        for(int j=0;j<len_c;j++) //需要进位的就进位
            if(c[j]>9) c[j+1]+=c[j]/10,c[j]%=10;
        if(c[len_c]) len_c++; //看最高位要不要进位
        len_ans=len_b,len_b=len_c,m=max(m,len_c); //把len_b赋值给len_ans,修改len_b的值,m为i阶乘的长度,看有没有进位
        for(int k=len_c-1;k>=0;k--) b[k]=c[k]; //把c存进b数组,即存进i的阶乘,下次循环b为i-1的阶乘
        len_c=len_a+len_ans;
        memset(c,0,sizeof(c)); //清零c数组,准备计算下个阶乘
        for(int j=0;j<m;j++){ //高精加,直接套模板
            f[j]+=b[j];
            if(f[j]>9) f[j+1]+=f[j]/10,f[j]%=10; //进位,注意不要写成f[j+1]++,f[j]-=10;就因为这里wa了一个点
        }
    }
    while(!f[m]&&m>0) m--; //去掉首导零
    for(int i=m;i>=0;i--) cout<<f[i]; //倒序输出
    return 0; //圆满结束
}

解释都在程序注释里


|