noj 1063 f数列 开方二分法.txt

NUAA ACM OJ源码

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

//NOJ 1063
//根据题目中给的提示，利用矩阵相乘解决费波纳须数列问题
//加快相乘速度的方法：分治法（用开方分治，二分法会超时）
typedef struct juzhen
{
    long a11;
    long a12;
    long a21;
    long a22;
}juzhen;

juzhen chen(juzhen mm,juzhen gg)
{	//返回矩阵mm和gg相乘的结果
    juzhen son;
    son.a11=(mm.a11*gg.a11+mm.a12*gg.a21)%10000;
    son.a12=(mm.a11*gg.a12+mm.a12*gg.a22)%10000;
    son.a21=(mm.a21*gg.a11+mm.a22*gg.a21)%10000;
    son.a22=(mm.a21*gg.a12+mm.a22*gg.a22)%10000;
    return son;
}

juzhen yuan={1,0,0,1};//次数为零的元矩阵

juzhen xian={1,1,1,0};//次数为1的元矩阵

juzhen cal(long num,juzhen ss)
{
    int i,yushu;
    juzhen first,second,third;
    if(num==0) return yuan;
    else if(num==1) return ss;
    else if(num==2) return chen(ss,ss);
    else
    {	//以下开方分治处理
	//将num看成i*i+yushu,则ss^(num)=ss^(i*i+yushu)=(ss^i)^i*ss^yushu
	//(这里的“*”表示矩阵相乘
	//即cal(num,ss)=chen(cal(i,cal(i,ss),cal(yushu,ss));
        i=sqrt(num);
        yushu=num-i*i;
        first=cal(i,ss);
        second=cal(i,first);
        third=cal(yushu,ss);
        return chen(third,second);
    }
}

int main()
{
    long num,answer;
    scanf("%ld",&num);
    while(num!=-1)
    {
        answer=((cal(num,xian)).a12)%10000;
        printf("%ld\n",answer);
        scanf("%ld",&num);
    }
    return 0;
}