Fibonacci数列的前几项为：1，1，2，3，5，8，13。

其规律是第i项是第i-1项与第i-2项的加和。

现在你的任务是对于给定的两个数字x和y，找到Fib[x]与Fib[y]的最小公倍数，其中Fib[i]为Fibonacci数列的第i项，F[1] = F[2] = 1。

应金老师的要求，你们可以尽情暴力这道题了。

Input
本题为多组数据输入。

每组数据只有两个整数x和y(0 < x,y <= 35)。

Output
输出一个整数代表Fib[x]与Fib[y]的最小公倍数。

Sample Input
1 2

1 3

Sample Output
1

2

#include <iostream>
using namespace std;
int F(int n)
{
   int F[47];
   F[1]=1;
   F[2]=1;
   for (int i=3;i<=n;i++)
   {
   F[i]=F[i-1]+F[i-2];
   }
   return F[n];
}
int hcf(int x, int y)
{
    if(x%y==0) return y;
    else return hcf(y,x%y);
}
int lcd(int x, int y)
{
    int c;
    c=x*y/hcf(x,y);
    return c;
}
int main()
{
    int a,b,n,m,x,y;
    while(cin >> a >> b)
    {x=F(a);
    y=F(b);
    n = hcf(x,y);
    m = lcd(x,y);
    cout << m << endl;}
    return 0;
}
样例都能过，但交上去就是答案错误，，，

[此贴子已经被作者于2019-12-21 20:08编辑过]

先在网上搜一下 Fib(35) 是多少，比如这个网站 http://www.
得知
Fib(34) = 5702887
Fib(35) = 9227465
又因为相邻两个斐波那契数的最大公约数是1（由“辗转相减法求最大公约数”可直接看出来）
所以 Fib[x]与Fib[y]的最小公倍数 的最大值是 5702887*9227465=52623190191455
打开任意一个计算器，计算 ln(52623190191455)/ln(2) = 45.58
所以我们有了第一个结论：结果类型最小是 uint64_t。

x*y 是不是会溢出也需要测试，既然不能确定，那为什么不写成 x/hcf(x,y)*y ？

C++ 标准模板库中有 std::gcd 和 std::lcm，即便你想自己写，也先看看别人是怎么实现的

[此贴子已经被作者于2019-12-22 11:36编辑过]

试了一下，还是答案错误😭

#include<stdio.h>
int main()
{
    int x, y;
    int num[36] = {0,1,1};
    for(int i = 3; i<=35; i++)
    {
        num[i] = num[i-1] + num[i-2];
    }
    while(~scanf("%d %d", &x, &y))
    {
        int temp;
        if(x<y)
        {
            temp = x;
            x = y;
            y = temp;
        }
        for(int i=num[x]; i>0; i++)
            if(i%num[x]==0 && i%num[y]==0)
            {
                printf("%d\n", i);
                break;
            }
    }
}
这个是一个学长讲的，但是超时了，，，，

你在说什么？

寻找有能力的开发 开发绝地求生游戏的某一方面的东西 有意可联系QQ643093820 你有实力我可以给你带来财富

就是按你的方法改，提交上去wrong answer了。。。

你连修改后的代码都不肯给，我怎么可能知道你哪里写错了？别浪费大家的时间行不行

当然，这不是你的错，而是这个论坛缺少拉黑功能。
你可能不希望我回答你的提问，但我没法知道这一点;
而我可能希望以后避开你的提问，可时间一长就会忘了。

#include <iostream>
using namespace std;
int F(int n)
{
   int F[47];
   F[1]=1;
   F[2]=1;
   for (int i=3;i<=n;i++)
   {
   F[i]=F[i-1]+F[i-2];
   }
   return F[n];
}
int hcf(int x, int y)
{
    if(x%y==0) return y;
    else return hcf(y,x%y);
}
int lcd(int x, int y)
{
    int c;
    c=x/hcf(x,y)*y ;


    return c;
}
int main()
{
    int a,b,n,m,x,y;
    while(cin >> a >> b)
    {x=F(a);
    y=F(b);
    n = hcf(x,y);
    m = lcd(x,y);
    cout << m << endl;}
    return 0;
}
//我是照着版主大大的原话改你的程序的可以运行

    int c;
    c=x/hcf(x,y)*y ;
这里 x/hcf(x,y)*y 可能会溢出，int存不下。
输入 34 35 试试看结果