/ OK / 题库 / 丑数 /

题解

1 条题解

  • 0
    @ 2017-03-15 20:37:18

    万恶的高精度。。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    using namespace std;
    struct num{
        int data[30];
        int len;
    num()
    {
        len=1;
        memset(data,0,sizeof(data));
    }
    num(int a)
    {
        len=0;
        while(a>0)
        {
            len++;
            data[len]=a%10;
            a/=10;
        }
        if(len==0)
        {
            data[1]=0;
            len=1;
        }
    }
    };
    num operator*(num a,num b)
    {
        num t;
        t.len=a.len+b.len-1;
        int y;
        for(int i=1;i<=a.len;i++)
        {
            int x=0;
            {
                for(int j=1;j<=b.len;j++)
                {t.data[i+j-1]=a.data[i]*b.data[j]+x+t.data[i+j-1];
                x=t.data[i+j-1]/10;
                t.data[i+j-1]=t.data[i+j-1]%10;}
                t.data[b.len+i]=x;y=x;
            }
        
        }   
        if(y>0)
            {
                t.len++;
                t.data[t.len]=y;
            }
        return t;
    }
    num  compare1(num a,num b)
    {
        if(a.len>b.len) return b;
        if(b.len>a.len) return a;
        if(a.len==b.len)
        for(int i=a.len;i>=1;i--){
            if(a.data[i]==b.data[i]) continue;
            if(a.data[i]<b.data[i]) return a;
            if(a.data[i]>b.data[i]) return b;
        }
        return a;
    } 
    num compare2(num a,num b,num c)
    {
        num t;
        t=compare1(a,b);
        t=compare1(t,c);
        return t;
    }
    bool compare3(num a,num b)
    {
        if(a.len!=b.len) return 0;
        for(int i=a.len;i>=1;i--)
            if(a.data[i]!=b.data[i]) return 0;
            return 1;
    }
    num a[10010],x[4],m;
    int main()
    {
        int n,c1,c2,c3;
        cin>>n;
        a[1]=1;c1=c2=c3=1;
        for(int i=2;i<=n;i++)
        {
            x[1]=a[c1]*2;
            x[2]=a[c2]*3;
            x[3]=a[c3]*5;
           a[i]=compare2(x[1],x[2],x[3]);
            if(compare3(a[i],x[1])==1) c1++;
            if(compare3(a[i],x[2])==1) c2++;
            if(compare3(a[i],x[3])==1) c3++;
        }
        for(int i=a[n].len;i>=1;i--)
        cout<<a[n].data[i];
        return 0;
    }
    
  • 1

信息

难度
8
分类
高精度 点击显示
标签
(无)
递交数
18
已通过
4
通过率
22%
上传者