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
0
0
周琪岳
资深光能
资深光能
嗨,汪恺恒(网卡还王卡桓),这题很难,我只做了90分,才学到循环的你(虽然你连贪心都会)还是放弃吧!要想刷难题,模拟贪心DP里题有的是
0