对于Fibonacci数列:1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题:第n项和第m项的最大公约数是多少?
Update:加入了一组数据。
输入格式:
两个正整数n和m。(n,m<=10^9)
注意:数据很大
输出格式:
Fn和Fm的最大公约数。
由于看了大数字就头晕,所以只要输出最后的8位数字就可以了。
用递归&递推会超时
用通项公式也会超时
题解:
emmmm,这题,我差不多错了十三四遍吧。
真是有成就感。
80分代码:
1 #include<iostream> 2 #include<cstdio> 3 #define ll long long 4 using namespace std; 5 ll n,m; 6 ll gcd(ll a,ll b){ 7 if(b==0)return a; 8 return gcd(b,a%b); 9 } 10 ll a[10000001]; 11 int main(){ 12 scanf("%lld %lld",&n,&m); 13 ll w=gcd(n,m); 14 a[1]=1; 15 a[2]=1; 16 for(int i=3;i<=w;i++) 17 a[i]=(a[i-1]+a[i-2])%100000000; 18 printf("%lld",a[w]); 19 return 0; 20 }
AC
,,迷一样,我是不会说出去的!
一世安宁
原文:https://www.cnblogs.com/GTBA/p/9183242.html