题解 P1249 【最大乘积】

· · 题解

一道不是很难的高精题目……

先回到最原始的P1601 A+B Problem（高精），

思路：设置三个无返回值型的函数，分别实现高精度读入、高精度加法和高精度输出。

高精度读入：用char类型数组输入，用int类型数组倒序存储数据（减去字符0），并用数组的第零位存储长度。

高精度加法：先不考虑进位问题，用一个新的数组把每一位两个数组的加和存储下来。

然后考虑进位问题，用下一位加上前一位除以十的结果，并把前一位模十（留个位）。

判断前导零：如果位数大于一（只有一位数“0”可以），并且首位等于零的话，就把数组长度减一。

高精度输出：因为当时是倒序存储的，所以要倒序循环输出数组的每一位。

最后，在主函数中调用三个函数即可。

易错：在倒序存储时由于数组第零位表示长度，要从1到以长度为下标的那一位存储。

那么，其实乘法与加法类似。

代码（高精度乘法）：

void cheng(int a[],int b,int c[]){
    c[0]=a[0];
    for(int i=1;i<=c[0];i++) c[i]=a[i]*b;
    for (int i=1;i<=c[0];i++){
        c[i+1]+=c[i]/10;
        c[i]%=10;
        if(c[c[0]+1]>0) c[0]++;
    }
}

回到这道题，不难得到如下思路：

用贪心从2开始递增累加ans，直到累加大于n。

然后把ans-n删掉，再用高精度累乘即可。

重要代码部分：

void read(int a[]){//读入
    char s[10005];
    cin>>s;
    a[0]=strlen(s);
    for(int i=0;i<a[0];i++){
        a[a[0]-i]=s[i]-'0';
    }
}
void add(int a[],int b[]){//高精度加法
    c[0]=max(a[0],b[0]);
    for(int i=1;i<=c[0];i++){
        c[i]=a[i]+b[i];
    } 
    for(int i=1;i<c[0];i++){
        c[i+1]+=c[i]/10;
        c[i]%=10;
    }
    while(c[0]>1&&c[c[0]]==0) c[0]--;
}
void print(int a[]){//输出
    for(int i=a[0];i>=1;i--){
        cout<<a[i];
    }
}

现在，有了这些铺垫，做这道题就很容易了。

AC代码：

#include<iostream>
using namespace std;
long long n,x=0,s1=0,i=2,t=1;
int a[10001];
int s[10001];
void cj(int x)
{
    for(int i=1;i<=t;i++)
        s[i]=s[i]*x;
    for(int i=1;i<=t;i++)
    {
        if(s[i]>=10)
        {
            long long x=s[i]/10;
            s[i+1]+=x;
            s[i]%=10;
            if(i+1>t) t=i+1;
        }
    }
}
int main()
{
    s[1]=1;
    cin>>n;
    while(s1<n)
    {
        a[++x]=i;
        s1+=i;
        i++;
    }
    a[s1-n-1]=0;
    for(int i=1;i<=x;i++)
    {
        if(a[i]!=0) cout<<a[i]<<' ';
        if(a[i]!=0) cj(a[i]);
    }
    cout<<endl;
    for(int i=t;i>=1;i--)
        cout<<s[i];
    return 0;
}

祝大家AC愉快！