首页 > 其他 > 详细

洛谷 P1306 斐波那契公约数

时间:2018-06-14 16:42:11      阅读:136      评论:0      收藏:0      [点我收藏+]

                         洛谷 P1306 斐波那契公约数

题目描述

对于Fibonacci数列:1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题:第n项和第m项的最大公约数是多少?

Update:加入了一组数据。

输入输出格式

输入格式:

两个正整数n和m。(n,m<=10^9)

注意:数据很大

输出格式:

Fn和Fm的最大公约数。

由于看了大数字就头晕,所以只要输出最后的8位数字就可以了。

输入输出样例

输入样例#1: 
4 7
输出样例#1: 
1

说明

用递归&递推会超时

用通项公式也会超时

题解:

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 }
View Code

 

AC

,,迷一样,我是不会说出去的!

一世安宁

 

洛谷 P1306 斐波那契公约数

原文:https://www.cnblogs.com/GTBA/p/9183242.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!