# bzoj4833

\$数论\$

\$这个题已经忘了怎么做了，也不想知道了，只记得看了3个小时\$

\$对于有gcd(f_i, f_j) = f_{gcd(i, j)}性质的数列，以下结论适用\$

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n;
ll ans = 1, P;
ll f[N], g[N];
int m[N];
int rd()
{
int x = 0, f = 1;
char c = getchar();
while(c < ‘0‘ || c > ‘9‘) { if(c == ‘-‘) f = -1; c = getchar(); }
while(c >= ‘0‘ && c <= ‘9‘) { x = x * 10 + c - ‘0‘; c = getchar(); }
return x * f;
}
ll power(ll x, ll t)
{
ll ret = 1;
for(; t; t >>= 1, x = x * x % P) if(t & 1) ret = ret * x % P;
return ret;
}
ll inv(ll x)
{
return power(x, P - 2);
}
int main()
{
int T = rd();
while(T--)
{
n = rd();
P = rd();
f[0] = 0;
f[1] = 1;
for(int i = 2; i <= n; ++i) f[i] = (f[i - 1] * 2 + f[i - 2]) % P;
for(int i = 1; i <= n; ++i) g[i] = f[i];
for(int i = 1; i <= n; ++i)
{
ll t = inv(g[i]);
for(int j = i + i; j <= n    ; j += i)
g[j] = g[j] * t % P;
}
ll lcm = 1;
ans = 0;
for(int i = 1; i <= n; ++i)
{
lcm = lcm * g[i] % P;
ans = (ans + 1LL * lcm * i) % P;
}
printf("%lld\n", ans);
}
return 0;
}```
View Code

bzoj4833

(0)
(0)

0条