问题标题: 酷町堂:3383

0
0
已解决
汪恺恒
汪恺恒
中级启示者
中级启示者

题目描述 Description

对于Fibonacci数列:1, 1, 2, 3, 5, 8, 13…,现在我们需要求第n项和第m项的最大公约数?

输入描述 Input Description

两个正整数n和m。

注意:数据很大

输出描述 Output Description

Fn和Fm的最大公约数。
只要输出最后的8位数字就可以了。

#include<iostream> 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std; 
long long n,x,y,ans[100],cnt,m,sum; 
long long gcd(int x,int y){
    while(x%y!=0){
        int r=x%y;
        x=y;
        y=r;
    } 
    return y;
}
int main(){ 
    cin>>n>>m;
    x=sqrt(5)/5*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n));
    y=sqrt(5)/5*(pow((1+sqrt(5))/2,m)-pow((1-sqrt(5))/2,m));
    sum=gcd(x,y);
    while(cnt<8&&sum){
        ans[++cnt]=sum%10;
        sum/=10;
    }
    for(int i=cnt;i>=1;i--){
        cout<<ans[i];
    }
    return 0; 
}

为什么错了??


0
已采纳
王子耀
王子耀
缔造者
缔造者

给你核心:

scanf("%d%d",&n,&m);
    int p=gcd(n,m);
    a[1]=1;a[2]=1;
    for(int i=3;i<=p;++i) a[i]=(a[i-1]+a[i-2])%100000000;
    printf("%d",a[p]); 

 

王子耀在2020-12-09 21:56:04追加了内容

你是不是没有注意下面的  数据范围及提示 Data Size & Hint  呀!

你的代码都超时了唉!

0
王子耀
王子耀
缔造者
缔造者

。。。我居然奇妙的AC了?!

0
0
周琪岳
周琪岳
资深光能
资深光能

嗨,汪恺恒(网卡还王卡桓),这题很难,我只做了90分,才学到循环的你(虽然你连贪心都会)还是放弃吧!要想刷难题,模拟贪心DP里题有的是

0
汪恺恒
汪恺恒
中级启示者
中级启示者

是3383!!!!不是3386!!

我要回答