SDUT 2568 小白学Fibonacci之一


		题目描述
一天，Z懂得了Fibonacci数列，发现数列有以下规律：
F[1]=F[2]=1; F[N]=F[N-1]+F[N-2];
于是Z觉得很神奇，想知道任意两个Fibonacci数有没有大于1的公约数。但是光在有限的范围内手算还不行，于是Z找到了你，希望你能帮忙编个程序算算。
任务：指定两个Fibonacci数的项数（也就是这两个数各是第几项），求出这两个数的最大公约数。
例如输入3 6，输出2（因为GCD(F[3],F[6])=2）。
输入
多组数据，每行两个数A，B。到文件末尾。
 0<A,B<100007
输出
每组数据输出一行。保证最后结果不超过2^64-1，所以使用64位无符号整数。
示例输入
30 15
14 28
12 24
17 17
30 6
24 24
20 10
24 12
29 29
9 18
示例输出
610
377
144
1597
8
46368
55
144
514229
34
 
    这道题目刚开始看到的时候我想的是辗转相减求公约数。 因为斐波那契是和的形式，于是我想用减法求公约数可以，可是实际划了一下，不可以，因为数太大了。
   接着又想到一一枚举。 将这题转换成大数求余数，这个很容易处理。 划了一下还是不行，因为，要枚举1到2的60多次方，除非是用二分。 否则肯定会死的很惨，而这题又用不上。所有就不知道怎么处理了。
  最后想到找规律，画了画斐波那契数列，果然存在着规律，发现： 如果一个斐波那契数是n，是第x个数，那么数n与第x+x，x+2*x,x+3*x....个的最大公约数就是n。根据这个规律就能做出这道题目来
[cpp]  
#include <stdio.h>  
#include <string.h>  
#include <math.h>  
int main()  
{  
    unsigned long long int res1,res2,res,max;  
    int i,j,n,m,s,t,pre;  
    int l,r;  
    while(scanf("%d %d",&l,&r)!=EOF)  
    {  
        if(l>r)  
        {  
            t=l; l=r; r=t;  
        }  
        if(l==1||l==2||r==1||r==2)  
        {  
            printf("1\n");  
            continue;  
        }  
        res1=1; res2=1; res=1;  
        if(l==r)  
        {  
            for(i=3;i<=l;i++)  
            {  
                res=res1+res2;  
                res1=res2;  
                res2=res;  
            }  
            printf("%llu\n",res);  
            continue;  
        }  
        max=1;  
        pre=1;  
        for(i=3;i<=l; i+=pre)  
        {  
            if((l%i==0)&&(r%i==0))  
            {  
                pre=i;  
                max=i;  
            }  
        }  
        res1=1; res2=1; res=1;  
        for(i=3;i<=max;i++)  
        {  
            res=res1+res2;  
            res1=res2;  
            res2=res;  
        }  
        printf("%llu\n",res);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,