大数记录之，大数乘整型数nyoj832

末蓝、 2022-09-17 10:26 74阅读 0赞

想到了一个题目：对决二[http://acm.nyist.net/JudgeOnline/problem.php?pid=832][http_acm.nyist.net_JudgeOnline_problem.php_pid_832]

但是发现有一道题目是相似的：[http://acm.nyist.net/JudgeOnline/problem.php?pid=541][http_acm.nyist.net_JudgeOnline_problem.php_pid_541]

但是答案是不一样的、我的代码交到战斗力题目上会wa....终于找到答案了，是求大数的代码有漏洞。

求大数的代码：刚开始没有加k=0,找好久错误。

int cheng(int x,int p)
    {
        int k;
        int t=p;
        for(int i=0,k=0;i<t;i++)
        {
            s[i]=s[i]*x+k;k=0;
            if(s[i]>=10)
            {
                if(i==t-1)
                    t++;
                int h=s[i];
                s[i]=s[i]%10;
                k=h/10;
            }
        }
        return t;
    }

别人的：

int cheng(int x,int p)//大数乘小数
    {
        int i,j,k,t;
        int temp = 0;
        int c = 0;t=p;
        for(i=0; i<t; i++)
        {
            temp = s[i]*x+c;
            if(i==p-1&&temp>=10)
                t++;
            s[i] = temp%10;
            c = temp/10;
        }
        return t;
    }

不加字符长度的：

int multiply(int x)//大数乘小数 
    {
        int i,j,k;
        int temp = 0;
        int c = 0;
        for(i=0; i<200; i++)
        {
            temp = ans[i]*x+c;
            ans[i] = temp%10; 
            c = temp/10;   
        }
    }

题意都是吧一个数n分成多个数的和，让多个数的和的乘积最大！

后来发现我的思路跟那道题目不一样，我的思路是，判断能分成3尽量分成3，分不了3的分成2。比如6分成2的话为2+2+2，乘积为2^3=8，而分成3的话为3+3，乘积为3\*3=9；

所以我先判断是不是奇数，是奇数的话先分成一个3，即n-3，变成偶数，然后在判断大于6的话，ans\*=9；n-=6;不大于6的话是否大于4，大于四的话ans\*=4;n-=4;然后大于2的情况也一样，直到为0.

果然思路是对的，是乘法搞错了。在好好看看、代码：

#include <stdio.h>
    #include <string.h>
    int s[100000];
    int cheng(int x,int p)//大数乘小数
    {
        int i,j,k,t;
        int temp = 0;
        int c = 0;t=p;
        for(i=0; i<t; i++)
        {
            temp = s[i]*x+c;
            if(i==p-1&&temp>=10)
                t++;
            s[i] = temp%10;
            c = temp/10;
        }
        return t;
    }
    /*int cheng(int x,int p)
    {
        int k;
        int t=p;
        for(int i=0,k=0;i<t;i++)
        {
            s[i]=s[i]*x+k;
            //printf("%d\n",s[i]);
            if(s[i]>=10)
            {
                if(i==p-1)
                    t++;
                int h=s[i];
                s[i]=s[i]%10;
                k=h/10;
            }
        }
        return t;
    }*/
    int main()
    {
    	int n,T;
    	scanf("%d",&T);
    	while(T--)
        {   scanf("%d",&n);
            memset(s,0,sizeof(s));
            int p=1;s[0]=1;
            if(n<4)
            {
                printf("%d\n",n);continue;
            }
            else
            {
                if(n%2)
                {
                    p=cheng(3,p);n-=3;
                }
                while(n>0)
                {
                    if(n>=6)
                    {
                        p=cheng(9,p);
                        n-=6;
                    }
                    else if(n>=4)
                    {
                        p=cheng(4,p);
                        n-=4;
                    }
                    else
                    {
                        p=cheng(2,p);
                        n-=2;
                    }
                }
    
            }
            for(int i=p-1;i>=0;i--)
                printf("%d",s[i]);
            printf("\n");
        }
        return 0;
    }

[http_acm.nyist.net_JudgeOnline_problem.php_pid_832]: http://acm.nyist.net/JudgeOnline/problem.php?pid=832
[http_acm.nyist.net_JudgeOnline_problem.php_pid_541]: http://acm.nyist.net/JudgeOnline/problem.php?pid=541