神奇数论题。
做这题需要知道两个结论：
- 对于满足\(f_{i+2}=a\cdot f_{i+1}+b\cdot f_{i}\)，也就是形式类似斐波那契数列的序列，有\(gcd(f_i,f_j)=f_{gcd(i,j)}\)(据说是这样，我不确定正确性，但至少这题中a=2,b=1的情况是对的)
- 对于一个集合\(S\)(可以是多重集)，有\(lcm(S)=\prod_{T\subset S,|T|>0} gcd(T)^{(-1)^{|T|+1}}\)。其实就是min-max容斥，对于因数中的每一个质数分别考虑，lcm是取这个质数出现次数的最大值，gcd是取最小值，符合min-max容斥的形式。
先转化一下题意：有一个序列\(f\)满足\(f_{i+2}=2f_{i+1}+f_i,f_0=0,f_1=1\)，令\(g_n=lcm(f_1,f_2\cdots f_n)\)，求\(\sum_{i=1}^n g_i\cdot i\)对\(p\)取模的值。
套用上面两个结论的式子：
\[\begin{align} g_n&=lcm(f_1\cdots f_n)\\ &=\prod_{T\subset S,|T|>0} (gcd_{i\in T} f_i)^{(-1)^{|T|+1}}\ \ S表示\{1,2,\cdots n\}的集合，注意不是\{f_1\cdots f_n\}\\ &=\prod_{T\subset S,|T|>0} (f_{gcd(T)})^{(-1)^{|T|+1}}\\ \end{align} \]设\(f_n=\prod_{d|n}h_d\)。注意是\(\prod\)不是\(\sum\)。
用\(h\)进一步简化式子：
\[\begin{align} g_n&=\prod_{T\subset S,|T|>0} (f_{gcd(T)})^{(-1)^{|T|+1}}\\ &=\prod_{T\subset S,|T|>0}(\prod_{d|gcd(T)} h_d)^{(-1)^{|T|+1}}\\ &=\prod_{d=1}^n (h_d)^{\sum_{T\subset S,|T|>0} (-1)^{|T|+1}}\ \ 其中要求T中元素都是d倍数\\ &=\prod_{d=1}^n (h_d)^{\sum_{|T|>0} (-1)^{|T|+1}}\ \ 其中要求T中元素\le\frac nd\\ &=\prod_{d=1}^n h_d\ \ 注意到后面的幂次永远=1\\ \end{align} \]这样，只要能求出序列\(h\)，这题就做完了。\(h\)可以从前往后构造，枚举到\(i\)时，令\(h_i=\frac {f_i}{\prod_{d|i,d\ne i}h_d}\)。
总时间复杂度\(O(nlogn)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
LL t,n,p,f[1000010],h[1000010];
bool vis[1000010];
LL qpow(LL x,LL a)
{
x%=p;if(x==0) return 0;
LL res=x,ret=1;
while(a>0)
{
if(a&1) (ret*=res)%=p;
a>>=1;
(res*=res)%=p;
}
return ret;
}
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
scanf("%lld%lld",&n,&p);
f[1]=1;for(int i=2;i<=n+3;++i) f[i]=(f[i-1]+f[i-1]+f[i-2])%p;
repn(i,n) h[i]=1;
repn(i,n)
{
h[i]=f[i]*qpow(h[i],p-2)%p;
for(LL j=i+i;j<=n;j+=i) (h[j]*=h[i])%=p;
}
LL ans=0;
repn(i,n)
{
(h[i+1]*=h[i])%=p;
(ans+=h[i]*i)%=p;
}
printf("%lld\n",ans);
}
termin();
}