Problem
Sol
容易得到
[f_n=e_{n-1}+f_{n-1},e_{n-1}=f_{n-1}+e_{n-1},f_1=e_1=1
]
那么
[f_n=2 imes sum_{i=1}^{n-1}f_i-f_{n-1}+1
]
又有
[f_{n+1}=2 imes sum_{i=1}^{n}f_i-f_{n}+1
]
相减得到 (f_{n+1}=f_n imes 2 + f_{n-1},f_1=1)
有结论 (gcd(a,b)=1) 时，形如 (f_i=af_{i-1}+bf_{i-2}) 的数列有性质 (gcd(f_i,f_j)=f_{gcd(i,j)})
大概可以这么证明
而 (lcm) 实际上是一个对于质因子的指数取 (max) 的操作
每个质因子分开考虑，然后最值反演
[lcm(S)=prod_{i}p_i^{sum_{Tsubset S}min(T_i)(-1)^{|T|+1}}=prod_{i}prod_{Tsubset S}p_i^{min(T_i)(-1)^{|T|+1}}
]
交换顺序得到
[lcm(S)=prod_{T subset S}gcd(T)^{(-1)^{|T|+1}}
]
其中 (S,T e phi)，(min(T_i)) 表示 (p_i) 这个因子的指数最小值
所以
[g_n=prod_{T subset S}f_{gcd(T)}^{(-1)^{|T|+1}}=prod_{d=1}^{n}f_{d}^{sum_{Tsubset S}[gcd(T)==d](-1)^{|T|+1}}
]
设 $$s_d=sum_{Tsubset S}gcd(T)==d^{|T|+1}$$
[h_i=sum_{i|d}^{n}s_d=sum_{Tsubset S}[i|gcd(T)](-1)^{|T|+1}=[cnt_i
e 0]=1
]
其中 (cnt_i) 表示 (i) 的倍数的个数
那么
[s_i=sum_{i|d}^{n}mu(frac{d}{i})h_d=sum_{i|d}^{n}mu(frac{d}{i})
]
那么
[g_n=prod_{d=1}^{n}f_{d}^{sum_{d|i}^{n}mu(frac{i}{d})}=prod_{d=1}^{n}prod_{d|i}^{n}f_d^{mu(frac{i}{d})}=prod_{i=1}^{n}prod_{d|i}f_d^{mu(frac{i}{d})}
]
(Theta(nlog n)) 预处理出 (prod_{d|i}f_d^{mu(frac{i}{d})}) 即可
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn(1e6 + 5);
int pr[maxn], num, ispr[maxn], mu[maxn], n, f[maxn], s[maxn], g[maxn], mod, ans, inv[maxn];
inline int Pow(ll x, int y) {
register ll ret = 1;
for (; y; y >>= 1, x = x * x % mod)
if (y & 1) ret = ret * x % mod;
return ret;
}
inline void Inc(int &x, int y) {
if ((x += y) >= mod) x -= mod;
}
int main() {
register int i, j, test;
mu[1] = 1, ispr[1] = 1;
for (i = 2; i <= 1000000; ++i) {
if (!ispr[i]) pr[++num] = i, mu[i] = -1;
for (j = 1; j <= num && i * pr[j] <= 1000000; ++j) {
ispr[i * pr[j]] = 1;
if (i % pr[j]) mu[i * pr[j]] = -mu[i];
else {
mu[i * pr[j]] = 0;
break;
}
}
}
mod = 1e9 + 7;
for (scanf("%d", &test); test; --test) {
scanf("%d%d", &n, &mod), ans = 0;
for (f[1] = 1, i = 2; i <= n; ++i) f[i] = (2LL * f[i - 1] + f[i - 2]) % mod;
for (g[0] = i = 1; i <= n; ++i) g[i] = 0, s[i] = 1, inv[i] = Pow(f[i], mod - 2);
for (i = 1; i <= n; ++i)
for (j = i; j <= n; j += i)
if (mu[j / i] == 1) s[j] = 1LL * s[j] * f[i] % mod;
else if (mu[j / i] == -1) s[j] = 1LL * s[j] * inv[i] % mod;
for (i = 1; i <= n; ++i) g[i] = 1LL * g[i - 1] * s[i] % mod;
for (i = 1; i <= n; ++i) Inc(ans, 1LL * i * g[i] % mod);
printf("%d
", ans);
}
return 0;
}