大致题意： 已知(e_i=e_{i-1}+2f_{i-1},f_i=e_{i-1}+f_{i-1})，设(g(n)=lcm_{i=1}^nf(n))，求(sum_{i=1}^ni imes g(i))。
前言
神仙题，这种东西我怎么可能想得到。。。
我不会推式子，我只是式子的搬运工。
递推式的化简
好吧，这一部分大概是我唯一自己推出来的式子。。。（也因此我的这一步要比别人麻烦许多）
考虑把(e_i)消去，然后我就采用了代入消元法，递归代入得到：
然后我们发现当最终(e)的下标变成(0)时，(f_i)就是这样一个递推式。
然而(sum)这项毕竟还是太麻烦了，考虑把它替换掉：
于是最终我们就得到了一个很简单的式子：
接下来，开始搬运式子。。。
(Min-Max)容斥的神奇应用
考虑到对于一个形如(f(i)=af(i-1)+bf(i-2))的式子，都有一个共同性质：
但问题在于这道题求的是(lcm)呀，这个性质怎么用呢？
因此，我们就要把(lcm)转化为(gcd)，这里神奇地使用了(Min-Max)容斥：
显然，此处(gcd)对应(Min)，(lcm)对应(Max)（相当于把因数看作集合），因此原本的(sum)变成了(prod)，且((-1)^{|T|+1})这个系数就飞上去变成了次数。
然后我们就可以得到：
这个式子看起来还是很复杂啊，因此还需要继续推。
“最精髓的一步”（闪指导(hl666)评）
我也不知道是怎么想到的，反正这里我们需要构造一个函数(h(x))满足：（怎么构造之后会介绍）
然后我们把这个东西代入原式，就得到了：
看到(d|n)这个东西，我们就不禁回想起莫比乌斯反演的基本套路，因此就会调整枚举顺序，改为枚举(d)：
注意一下，此时的(S')表示({d,2d,3d,...,lfloorfrac nd
floor imes d})这个集合。（实际上它是什么集合都无所谓）
还有，原先的(prod)，飞到上面去就变成了(sum)。
然后我们仔细看看这个式子，就会发现，这个式子依旧很复杂，依旧不知道该怎么搞。
全体起立，思路清奇（闪指导(hl666)语）
让我们单独拎出此时的次数，如果我们去枚举(|T|)，就会得到这样一个东西：
是不是立刻觉得有蹊跷？若我们把(i)改为从(0)开始枚举，那么就多出一项(-1)，则我们在式子后面补上一个(1)使原式值不变得到：
然后我们就会发现，(sum_{i=0}^{|S'|}(-1)^{i+1}C_{|S|}^i)实际上是等于(0)的！
于是我们就得到了：
看着这个式子，尽管我们是一步一步有理有据推导过来的，是不是仍然有种不可置信的感觉？
莫比乌斯反演的神奇应用（(h(x))的构造）
众所周知，莫比乌斯反演是长这样子的一个式子：
然后放在这题里，实际上我们有这样一个推论：
由此我们可以发现，在这道题中很多我们曾熟悉，或自以为熟悉的公式，都因为(sum)变成了(prod)，而变得如此陌生。
这也启发了我，学习一个式子真的需要深层地去了解，从而能更灵活的应用。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 3000000
using namespace std;
int n,X,f[N+5],h[N+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
class LinearSieve//线性筛，筛莫比乌斯函数
{
private:
int Pt,P[N+5],mu[N+5];
public:
I int operator [] (CI x) Con {return mu[x];}
I LinearSieve()
{
mu[1]=1;for(RI i=2,j;i<=N;++i)
for(!P[i]&&(mu[P[++Pt]=i]=-1),j=1;j<=Pt&&i*P[j]<=N;++j)
if(P[i*P[j]]=1,i%P[j]) mu[i*P[j]]=-mu[i];else break;
}
}Mu;
int main()
{
RI Tt,i,j,g,Inv,ans;scanf("%d",&Tt);W(Tt--)
{
for(scanf("%d%d",&n,&X),i=1;i<=n;++i) h[i]=1;//初始化清空
for(f[1]=1,i=2;i<=n;++i)//递推f，同时求出h
{
Inv=QP(f[i]=(2LL*f[i-1]+f[i-2])%X,X-2);//递推f，计算逆元
for(j=1;i*j<=n;++j) Mu[j]&&(h[i*j]=1LL*h[i*j]*(~Mu[j]?f[i]:Inv)%X,0);//枚举倍数，更新h
}
for(ans=0,g=i=1;i<=n;++i) g=1LL*g*h[i]%X,ans=(1LL*i*g+ans)%X;//计算g,统计答案
printf("%d
",ans);//输出答案
}return 0;
}