1 条题解

  • 0
    @ 2025-10-8 16:50:19
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e4+10; 
    struct node
    {
        int a[N],len;
        node(){len=1;memset(a,0,sizeof(a));}
    };
    int cmp(node &n1,node &n2,int last)//n1以下标last为最低位,是否大于等n2
    {
        if (n1.a[last+n2.len]>0) return 1;
        for (int i=n2.len;i>=1;i--)
        {
            if (n1.a[last+i-1]>n2.a[i]) return 1;
            if (n1.a[last+i-1]<n2.a[i]) return -1;
        }
        return 0;
    }
    void div(node n1,node n2,node &n3,node &n4) //n1/n2 =n3余n4
    { 
        n4=n1;n3.len=n1.len-n2.len+1;
        for(int i=n3.len;i>=1;i--)// 计算商的第 i 位
        {
            while(cmp(n4,n2,i)>=0)// 若可以减,则减
            {
                for(int j=1;j<=n2.len;j++)//高精度减法 
                {
                    n4.a[i+j-1]-=n2.a[j];
                    if(n4.a[i+j-1]<0)
                    {
                        n4.a[i+j]-= 1;
                        n4.a[i+j-1]+= 10;
                    }
                } 
                n3.a[i]++;//商的这一位增加 1
            }
        }
        while(n3.a[n3.len]==0 && n3.len>1) n3.len--;
        while(n4.a[n4.len]==0 && n4.len>1) n4.len--;
    }
    char s[N];
    int main()
    {
        node n1,n2,n3,n4;
        scanf("%s",s+1);
        n1.len=strlen(s+1);
        for(int i=1; i<=n1.len; i++)n1.a[n1.len-i+1]=s[i]-'0';
        scanf("%s",s+1);
        n2.len=strlen(s+1);
        for(int i=1; i<=n2.len; i++)n2.a[n2.len-i+1]=s[i]-'0';
    
        div(n1,n2,n3,n4);
        
        for(int i=n3.len; i>=1; i--)printf("%d",n3.a[i]);
        printf("\n");
    
        return 0;
    }
    
    • 1

    信息

    ID
    397
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    122
    已通过
    34
    上传者