一开始数据没加强，一个简单的程序可以拿过
gcd(f[n],f[m])=f[gcd(n,m)]
下面这个是加强数据之后的80分代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; } int main() { ll n,m,a=1,b=1,c=1;cin>>n>>m; for(ll i=2;i<gcd(n,m);i++) { c=(a+b)%100000000; a=b; b=c;//cout<<c%100000000<<endl; } cout<<c%100000000; return 0; }//1 1 2 3 5
最后一个点TLE，吸氧了之后还是过不了
因此是算法的问题
我这个蒟蒻不会优化，于是看了题解
题解给的是矩阵的优化
蒟蒻并不会这个算法
下面是神仙程序
#include<cstdio> #include<cstring> #include<algorithm> #define ymw 100000000 using namespace std;long long n,m; struct node{long long a[3][3],r,c;}; inline node mul(node x,node y)//x*y的结果返回给z { node z; memset(&z,0,sizeof(z)); for(register int i=0;i<x.r;i++) for(register int j=0;j<y.c;j++) for(register int k=0;k<x.c;k++) z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%ymw; z.r=x.r;z.c=y.c; return z; } inline long long ksm(long long y)//快速幂加速递推 { node x,ans; memset(&x,0,sizeof(x)); memset(&ans,0,sizeof(ans)); x.r=x.c=ans.c=2; ans.r=1; x.a[0][0]=x.a[1][0]=x.a[0][1]=1; ans.a[0][0]=ans.a[0][1]=1; while(y) { if(y&1) ans=mul(ans,x); x=mul(x,x); y>>=1; } return ans.a[0][0]; } signed main() { scanf("%lld%lld",&n,&m); n=__gcd(n,m);//计算 if(n<3) return putchar(49)&0;//特判 printf("%lld",ksm(n-2));//输出 }