$數論$

$這個題已經忘了怎么做了，也不想知道了，只記得看了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

?

轉載于:https://www.cnblogs.com/19992147orz/p/8452289.html

總結

以上是生活随笔為你收集整理的bzoj4833的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。