题解 P2626 【斐波那契数列（升级版）】

『　』 · 2017-07-22 17:23:57 · 题解

不需要用递推求第n项，直接用通项公式（比内公式）

f(n)=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}

证明过程出门左转百度百科

https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define For(i,a,b)  for(i=a;i<=b;i++)
#define Forr(i,a,b)  for(i=a;i>=b;i--)
using namespace std;
long long  f[50];
void do1(int x)
{
    if(x==1)
    {
        printf("1");return;//特判1
    }
    if(x==2)
    {
        printf("2");return;//特判2
    }
    int k=x,i;
    for(i=2;i*i<=k;i++)//枚举比√k小的数
    {
        if(k%i==0&&k!=i)//能整出，为质因数，输出
        {
                printf("%d*",i);
                k/=i;//缩小
                i--;//处理多个质因数相等
        }
    }
    printf("%d",k);//输出k本身（现在本身也是个质因数了）
}
int main()
{
    int n,ans=0,m=0,k,i,j,t;
    scanf("%d",&n);
    f[n]=((1/sqrt(5))*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n)));//计算第n项，sqrt是根号（开方）,pow是乘方
    f[n]%=2147483648;//取模（直接在上面取不知道为什么会报错）
    printf("%lld=",f[n]);
    do1(f[n]);//分解质因数
    return 0;
}