题目描述

傻牛最近钻研各类数学递推数列。尤其是斐波那契数列。
傻牛眼中的斐波那契数列是这样的,F1=1,F2=1,然后Fi+2=Fi+1 + Fi,逐项递推。
今天,傻牛发现,某些斐波那契项之间是成倍数关系的。例如第4项F4=3和第8项F8=21。傻牛想知道,对于某一项Fx,求所有满足Fx是Fi倍数的i的和是多少?
数据范围:x小于等于1e6,数据组数小于等于1e5

题目分析

斐波那契数列是一个神奇的东西
首先我们 打表可知 证明一个结论:

预备结论

1.斐波那契数列第i项和第i-1项互质(显然)
2.$F_i=F_x * F_{i-x+1} +F_{x+1} * F_{i-x}$
第二条怎证明呢?很简单:
首先$F_i=F_1 * F_{i-2}+F_2 * F_{i-1}$是显然的对不对?
而$F_2=F_1+F_0$,$F_{i-3}=F_{i-2}-F_{i-4}$,$F_3=F_2+F_1$,$F_{i-2}=F_{i-1}-F_{i-3}$是的吧。
我们把这个式子$F_2 * F_{i-3} + F_3 * F_{i-2}$变形并化简得到:
$$F_1 * F_{i-2}+F_2 * F_{i-1}+(F_0 * F_{i-2}-F_1 * F_{i-4}-F_0 * F_{i-4}-F_2 * F_{i-3}-F_1 * F_{i-3}+F_1 * F_{i-1})$$
如果式子被吞了请打开图片查看。
好的,前面的就不看了,现在我们想想怎么搞掉括号里的,只看括号,由于$F_0=0$,然后再合并合并可得:
$$F_1 * F_{i-1}-F_2 * F_{i-3} -F_1 * (F_{i-4}+F_{i-3})$$
啊啊,$F_{i-4}+F_{i-3}$是什么?Fi-2啊!

$$F_1 * (F_{i-1}-F_{i-2})-F_2 * F_{i-3}$$
$F_{i-1}-F_{i-2}$是什么?$F_{i-3}$啊!
所以:
$$(F_1-F_2) * F_{i-3}$$
而$F_1-F_2$等于0吧?后面的括号被我们搞掉了!继续改变x的值的方法也差不多,就是合并的步骤多一些。

开始推导

好,对于n(n大于2):
假设$F_m=F_{m-n+1} * F_n+F_{m-n}* F_{n+1} $
首先由预备结论第一条,$F_n$和$F_{n+1}$是互质的对吧?
那么如果$F_m$是$F_n$的倍数,那么$F_{m-n}$是$F_n$的倍数
$F_n$是$F_n$的倍数,要使$F_{m-n}$是$F_n$的倍数,第一个这样的$m$是$2n$,第二个就是$3n$了,以此类推。
因此我们得到了做这题的方法:求题目给出的x的所有约数和即可。注意如果这个数是奇数,还要加个2(因为 $F_2=1$ )
然而考试时我是打表得到这些结论的,所以这题还是hin水的对吧

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;
#define LL long long
int ans[1000005];int n;
int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    for(int i=1;i<=1000000;i++)ans[i]=3;
    for(int i=3;i<=1000000;i++)
        for(int j=i;j<=1000000;j+=i)ans[j]+=i;
    while(scanf("%d",&n)!=EOF)printf("%d\n",ans[n]);
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *