讨论 / 题解...
wrongnumber 2014-07-04 02:17:05
点我顶贴 收藏 删除
引理1:

Gcd(F[n+1],F[n])=1;

证明:

根据辗转相减法则

Gcd(F[n+1],F[n])

=Gcd(F[n+1]-F[n],F[n])

=Gcd(F[n],F[n-1])

=Gcd(F[2],F[1])

=1

引理2:

F[m+n]=F[m-1]F[n]+F[m]F[n+1]

证明:

F[n+m]

=F[n+m-1]+F[n+m-2]

=2*F[n+m-2]+F[n+m-3]

=……

F[n+m]

=a[x]*F[n+m-x]+b[x]*F[n+m-x-1];

=a[x]*(F[n+m-x-1]+F[n+m-x-2])+b[x]*(F[n+m-x-1);

=(a[x]+b[x])*F[n+m+x-1]+a[x]*F[n+m+x-2];

当x=1时有 a[1]=F[2]; b[1]=F[1];

当x=2时有 a[2]=F[2]+F[1]=F[3]; b[2]=a[1]=F[2];

当x=k+1时有 a[k+1]=a[k]+b[k]=F[k+1]+F[k]=F[k+2] b[k+1]=a[k]=F[k+1];

所以当x=n时有

F[n+m]=a[n]F[m]+b[n]F[m-1];

=F[n+1]F[m]+F[n]F[m-1];

引理3:

Gcd(F[n+m],F[n])=Gcd(F[n],F[m])

证明:

Gcd(F[n+m],F[n])

=Gcd(F[n+1]F[m]+F[n]F[m-1],F[n]);

=Gcd(F[n+1]F[m],F[n]);

=Gcd(F[n+1],F[n])*Gcd(F[m],F[n])

=Gcd(F[m],F[n]);

于是显然有:Gcd(F[n],F[m])=F[Gcd(n,m)];

于是这就成了算斐波那契数的某一项.....

但这“某一项”可能就是10^9次方项 .....

1.倘若直接使用定义 即 a[n]=a[n-1]+a[n-2] 则超时

2.倘若求通项公式 但是斐波那契是有名的无理数表有理数的公式 无法取模 何况精度还有问题.....

3.用矩阵乘法+快速幂 复杂度由线性降至log级别

注意:矩阵乘法必须用long long 不然会跪...

#1 wrongnumber@2014-07-04 06:11:01
回复 删除
另外 当要求的项数>39的时候 输出八位要补0......
查看更多回复
提交回复