站外题求调

回复帖子

@HandSome_Peng 2021-04-08 13:06 回复

QAQ题目在这

无论是打表,还是数学证明,都能得到其实求的是斐波那契数列,所以思路是直接暴力求,但数据太大,要打压位高精,普通高精会TLE。

但我打的高精挂了五十分,数据太大不好调(数据在题目的附件里),自己看又找不出BUG,求助各位dalao。

(ps:这是我第一次打压位高精,可能会有大BUG,dalao们轻点喷

这是我的代码,50分,求调:

#include<bits/stdc++.h>
using namespace std;
#define RI register int
#define ll unsigned long long
#define MAXN 12666
const int mod=100000000;
char ch[MAXN];
int n[MAXN],a[MAXN],b[MAXN],c[MAXN],t[MAXN];
int x,tt,kk,len,sk,sl;
inline bool check(){
    if(b[0]<n[0])
        return false;
    if(b[0]>n[0])
        return true;
    for(RI i=n[0];i>=1;i--){
        if(b[i]<n[i])
            return false;
        if(b[i]>n[i])
            return true;
    }
    return true;
}
inline void add(){
    x=0;
    for(RI i=1;i<=b[0];i++){
        c[i]+=(x+a[i]+b[i]);
        x=c[i]/mod;
        c[i]%=mod;
    }
    c[0]=b[0];
    if(x!=0)
        c[++c[0]]=x;
    for(RI i=1;i<=a[0];i++)
        t[i]=a[i];
    t[0]=a[0];
    for(RI i=1;i<=b[0];i++)
        a[i]=b[i];
    a[0]=b[0];
    for(RI i=1;i<=c[0];i++)
        b[i]=c[i];
    b[0]=c[0];
    memset(c,0,c[0]+10);
    return;
}
inline void print(int x[]){
    for(RI i=x[0];i>=1;i--){
        tt=0,kk=1;
        for(RI j=1;j<=8;j++){
            tt+=((x[i]%10)*kk);
            x[i]/=10;
            kk*=10;
        }
        sk=tt,sl=8;
        while(sk!=0){
            sl--;
            sk/=10;
        }
        if(i!=x[0]&&sl>0)
            while(sl--)
                printf("0");
        printf("%d",tt);
    }
    printf("\n");
    return;
}
int main(){
//  freopen("euclid.in","r",stdin);
//  freopen("euclid.out","w",stdout);
    scanf("%s",ch);
    len=strlen(ch);
    for(RI i=len-1;i>=0;i--){
        if((len-i)%8==1){
            n[0]++;
            kk=1;
        }
        n[n[0]]+=(kk*(int)(ch[i]-'0'));
        kk*=10;
    }
    a[1]=0,a[0]=1;
    b[1]=1,b[0]=1;
    while(true){
        add();
        if(check()){
            print(t);
            print(a);
            break;
        }
    }
    return 0;
}
@saxiy 2021-04-08 15:28 回复 举报

Python香啊,压位高精背板子就行了啊,而且最好写到一个class里面,方便调试还可以复用。

@saxiy 2021-04-08 17:01 回复 举报

Python参考代码

class mat:
    def __init__(self,lu=1,ru=0,ld=0,rd=1):
        self.lu=lu
        self.ru=ru
        self.ld=ld
        self.rd=rd

def mul(a,b):
    lu=a.lu*b.lu+a.ru*b.ld
    ru=a.lu*b.ru+a.ru*b.rd
    ld=a.ld*b.lu+a.rd*b.ld
    rd=a.ld*b.ru+a.rd*b.rd
    return mat(lu,ru,ld,rd)

def Fb(n):
    res=mat()
    a=mat(1,1,1,0)
    while n!=0:
        #print('now:',n)
        if n%2==1:
            res=mul(res,a)
        a=mul(a,a)
        n=n//2
    return res

n=int(input())
ans=Fb(n)
print(ans.rd)
print(ans.ru)

我不知道是文件操作有问题还是怎么,交上去全wa了,但是要说斐波拉契的话就是这个。

@HandSome_Peng 2021-04-09 20:28 回复 举报

还有,我之前没说清楚,题目的意思是找到比 $n$(就是输入的数)大的第一个 $F_n$,然后输出 $F_{n-2}$和 $F_{n-1}$

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。