DDOSvoid's Blog

The Hangzhou Normal U Qualification Trials for ZJPSC 2021 B Baom and Fibonacci

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

题目描述

https://codeforces.com/gym/103462/problem/B

简要题意：给定 $n$，求 $\sum_{i=1}^n\sum_{j=1}^n gcd(fib(i), fib(j))$

$n\le 10^{10}$

Solution

我们知道 $gcd(fib(i), fib(j))=fib(gcd(i,j))$，那么我们容易化简得到 $ans=\sum_{t=1}^nfib(t)\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{t}\rfloor}[(i,j)=1]$，后面那两个 $\sum$，如果我们套用传统的 $\mu$ 去化简的话是不容易处理的，但我们注意到 $\sum$ 的上指标相同，能够想起一个经常被遗忘的式子 $\sum_{i=1}^n\sum_{j=1}^n[(i,j)=1]=2\sum_{i=1}^n\varphi(i)-1$,

我们令 $S(n)$ 表示 $\varphi$ 的前缀和，那么原式就是 $\sum_{i=1}^nfib(i)S(\lfloor\frac{n}{i}\rfloor)$，相当于是一个数论分块套杜教筛，时间复杂度为 $O(n^{\frac{2}{3}})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <cstring>
#include <cmath>
#define maxn 1000010
#define ll long long
using namespace std;

const int p = 998244353;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
inline int add(initializer_list<int> lst) { int s = 0; for (auto t : lst) s = add(s, t); return s; }
inline int mul(initializer_list<int> lst) { int s = 1; for (auto t : lst) s = mul(s, t); return s; }
int pow_mod(int x, ll n) {
    int s = 1;
    for (; n; n >>= 1, x = mul(x, x))
        if (n & 1) s = mul(s, x);
    return s;
}


int pri[maxn], phi[maxn], cnt; bool isp[maxn];
void init_isp(int n) {
    phi[1] = 1; 
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, phi[i] = i - 1; 
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = pri[j] * phi[i];
                break; 
            } phi[i * pri[j]] = (pri[j] - 1) * phi[i]; 
            
        }
    }
    for (int i = 1; i <= n; ++i) phi[i] = add(phi[i], phi[i - 1]); 
}

const int inv2 = pow_mod(2, p - 2); 
inline int F1(ll n) { n %= p; return mul({ (int) n, (int) n + 1, inv2 }); }

namespace Phi {
    const int N = 1000000; // n ^ 2/3
    ll n; int g[maxn]; bool vis[maxn]; int sn; // n ^ 1/2

    void init(ll _n) {
        n = _n; sn = sqrt(n);
        for (int i = 1; i <= 2 * sn; ++i) vis[i] = 0; 
    }
    int get(ll x) { return x <= sn ? x : sn * 2 - n / x + 1; }
    int calc(ll n) {
        if (n <= N) return phi[n];
        int id = get(n); if (vis[id]) return g[id];
        int ans = F1(n); 
        for (ll l = 2, r; l <= n; l = r + 1) {
            r = n / (n / l);
            ans = add(ans, p - mul((r - l + 1) % p, calc(n / l)));
        }
        return vis[id] = 1, g[id] = ans;
    }
}

namespace Fib {
    struct Matrix {
        static const int n = 2; 
        int a[n + 1][n + 1];
    
        Matrix() { clear(); }
        inline void setone() { clear(); for (int i = 1; i <= n; ++i) a[i][i] = 1; }
        inline void clear() { fill(a[0], a[0] + (n + 1) * (n + 1), 0); }
        friend Matrix operator * (const Matrix &u, const Matrix &v) {
            Matrix w; 
            for (int k = 1; k <= n; ++k)
                for (int i = 1; i <= n; ++i)
                    for (int j = 1; j <= n; ++j)
                        w.a[i][j] = add(w.a[i][j], mul(u.a[i][k], v.a[k][j]));
            return w;
        }
    }; 
    Matrix pow(Matrix x, ll n) {
        Matrix s; s.setone();
        for (; n; n >>= 1, x = x * x)
            if (n & 1) s = s * x;
        return s;
    }
    int calc(ll n) {
        Matrix x, s; x.a[1][1] = x.a[1][2] = x.a[2][1] = 1; s.a[1][1] = s.a[2][1] = 1;
        return add((pow(x, n) * s).a[1][1], p - 1);
    }
}

ll n; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; int ans = 0; Phi::init(n); init_isp(1000000);
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans = add(ans, mul(add(Fib::calc(r), p - Fib::calc(l - 1)), Phi::calc(n / l)));
    } cout << add(mul(2, ans), p - Fib::calc(n)) << "\n";
    return 0; 
}