P4240 毒瘤之神的考验

发表于 | 阅读数

$1 \le T \le {10}^4$
$1 \le n, m \le {10}^5$

令$n<m$

套路$T=xd$

$Case=1$。

直接预处$g(x,y)= \sum_{i=1}^{x} \phi(yi)$

$xy\leq 10^5$,预处理是$O(n\log n)$

$\sum_{x|T} \frac{x}{\phi(x)}\mu (\frac{T}{x})$

也是$O(n\log n)$可以预处理的

复杂度$O(B^2n+n\log n +T(\frac{n}{B}+\sqrt{n}))$

根据小学不等式可以知道$B=T^{\frac{1}{3}}$

最大复杂度若$T=\frac{n}{10},O(n^{\frac{5}{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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e5 + 10;
const int mod = 998244353;

int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }

int pcnt, pr[N], npr[N];
int mu[N], phi[N];

void Prime_init(int X)
{
    npr[1] = 1;
    mu[1] = 1;
    phi[1] = 1;
    for (int i = 1; i <= X; i++)
    {
        if (!npr[i])
            pr[++pcnt] = i, mu[i] = -1, phi[i] = i - 1;
        for (int j = 1; j <= pcnt && pr[j] * i <= X; j++)
        {
            npr[pr[j] * i] = 1;

            if (i % pr[j] == 0)
            {
                phi[pr[j] * i] = phi[i] * pr[j];
                mu[pr[j] * i] = 0;
                break;
            }
            else
            {
                phi[pr[j] * i] = phi[i] * (pr[j] - 1);
                mu[pr[j] * i] = mu[i] * (-1);
            }
        }
    }
}
int f[N];
vector<int> g[N];
int inv[N];
vector<int> T[30][30];

int B;
void init()
{
    int z = 1e5;

    Prime_init(1e5);
    inv[1] = 1;
    for (int i = 2; i <= z; i++)
        inv[i] = mod - 1LL * (mod / i) * inv[mod % i] % mod;
    for (int i = 1; i <= z; i++)
        for (int j = i; j <= z; j += i)
            f[j] = inc(f[j], 1ll * (mod + mu[j / i]) % mod * i % mod * inv[phi[i]] % mod);
    for (int i = 1; i <= z; i++)
    {
        int o = z / i + 1;
        vector<int> tmp(o + 1);
        for (int j = 1; j <= o; j++)
            tmp[j] = inc(tmp[j - 1], phi[i * j]);
        g[i] = tmp;
    }
    B = 23;

    for (int x = 1; x <= B; x++)
        for (int y = 1; y <= B; y++)
        {
            int o = z / max(x, y);
            T[x][y] = vector<int>(o + 1);
            for (int i = 1; i <= o; i++)
                T[x][y][i] = inc(T[x][y][i - 1], 1ll * g[i][x] * g[i][y] % mod * f[i] % mod);
        }
}
int solve(int n, int m)
{
    if (n > m)
        swap(n, m);
    int res = 0;
    int pos = n + 1;
    for (int i = 1; i <= n; i++)
    {
        if (m / i <= B && n / i <= B)
        {
            pos = i;
            break;
        }
        res = inc(res, 1ll * g[i][n / i] * g[i][m / i] % mod * f[i] % mod);
    }

    for (int i = pos, j; i <= n; i = j + 1)
    {
        j = min(n / (n / i), m / (m / i));
        res = inc(res, del(T[n / i][m / i][j], T[n / i][m / i][i - 1]));
    }
    return res;
}
int read()
{
    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 << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

int main()
{
    int T = read();
    init();
    while (T--)
    {
        int n = read(), m = read();
        printf("%d\n", solve(n, m));
    }
}