题目描述

傻牛最近钻研各类数学递推数列。尤其是斐波那契数列。
傻牛眼中的斐波那契数列是这样的，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}$是什么？F_i-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;
}