C 形阵 - 加强版 - 题目列表

C 形阵 - 加强版

GitHub跳转原题关系图 Canvas 关系图返回列表

使用与 C 形阵基础版相同的乘法函数容斥和 Min_25 质因数递归，支持 n<=10^10。

OJ: shumeng

题目 ID: CSP202512D2

难度:未知

标签:数论Min_25 筛乘法函数质因数分解容斥

日期: 2026-07-31 16:22

形式化题目

与 C 形阵（CSP202512D）完全相同，仅将 $n$ 的范围上限从 $10^7$ 提高到 $10^{10}$ 。求大小不超过 $n$ 的 C 形阵价值总和，或其中完美 C 形阵的价值总和，对 $998244353$ 取模。

思路

沿用基础版的核心推导，不再重复：由 $AC=B^2$ 和 $B=F$ 把七元组参数化为质因子指数上的局部选择 $(x,y)$ ，使每个方案的价值成为乘法函数；完美条件对应六个指数向量线性关系，任意两两交集为 $X=Y=0$ ，用容斥公式统计。

处理更大的 n

$n$ 增大到 $10^{10}$ 后，枚举所有 $B$ 不再可行。基础版已经把答案改写为 6 个乘法函数的前缀和，这里直接用整除分块加上 Min_25 筛处理：质数部分的基函数前缀用 Min_25 递推得到，再递归枚举最小质因子统计乘法函数前缀和。

实现要点

整除分块状态数约 $O(\sqrt n)$ ，用 small_id/large_id 映射；
每个素数的各次幂预计算 6 种局部函数值；
递归求解用哈希表缓存 (value, first_prime) 避免重复计算。

代码

cpp

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 23:08
 */
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353LL;

long long limit_n;
vector<int> primes;                      // 不超过 sqrt(n) 的素数
vector<int> small_id;                    // 整除分块值小的一半 -> 状态下标
vector<int> large_id;                    // 整除分块值大的一半 -> 状态下标
vector<long long> quotient_values;       // 所有 n/i 的整除分块值
vector<vector<long long>> prime_sieve_sum; // Min_25 筛的 4 个质数幂前缀和
vector<array<long long, 6>> prime_prefix;  // 素数处的 6 种局部函数前缀和
vector<vector<array<long long, 6>>> local_values; // 每个素数的各次幂的局部函数值
unordered_map<unsigned long long, array<long long, 6>> memo; // 递归求值缓存

// 取余并规整到 [0, MOD) 区间
long long normalize(long long value) {
    value %= MOD;
    if (value < 0) value += MOD;
    return value;
}

// 整除分块值 value 对应的状态下标
int quotient_id(long long value) {
    if (value <= (long long)small_id.size() - 1) return small_id[value];
    return large_id[limit_n / value];
}

// 6 个乘法函数在 value 处的质数部分之和（仅含素数与素数次幂的贡献）
array<long long, 6> prime_sum(long long value) {
    array<long long, 6> result{};
    if (value < 2) return result;
    int id = quotient_id(value);
    long long p0 = prime_sieve_sum[0][id];
    long long p1 = prime_sieve_sum[1][id];
    long long p2 = prime_sieve_sum[2][id];
    long long p3 = prime_sieve_sum[3][id];
    result[0] = normalize(p3 + 2 * p2 + 3 * p1 + 2 * p0);
    result[1] = normalize(p2 + p1 + p0);
    result[2] = normalize(p3 + p1);
    result[3] = normalize(3 * p1);
    result[4] = p1;
    result[5] = p1;
    return result;
}

// 递归统计 6 个乘法函数不超过 value 的前缀和，first_prime 限制最小质因子从第几个素数开始
array<long long, 6> solve_sum(long long value, int first_prime) {
    array<long long, 6> zero{};
    if (value < 2) return zero;
    if (first_prime >= (int)primes.size()) {
        array<long long, 6> answer = prime_sum(value);
        int count = upper_bound(primes.begin(), primes.end(), (int)value) -
            primes.begin();
        for (int type = 0; type < 6; type++) {
            answer[type] = normalize(answer[type] -
                prime_prefix[count][type]);
        }
        return answer;
    }
    if (primes[first_prime] > value) return zero;

    unsigned long long key =
        (unsigned long long)value * (primes.size() + 1ULL) + first_prime;
    unordered_map<unsigned long long, array<long long, 6>>::iterator found =
        memo.find(key);
    if (found != memo.end()) return found->second;

    array<long long, 6> answer = prime_sum(value);
    int count = upper_bound(primes.begin(), primes.end(), (int)value) -
        primes.begin();
    int prefix_count = min(first_prime, count);
    for (int i = 0; i < 6; i++) {
        answer[i] = normalize(answer[i] - prime_prefix[prefix_count][i]);
    }

    for (int prime_index = first_prime;
         prime_index < (int)primes.size() &&
         (long long)primes[prime_index] <= value / primes[prime_index];
         prime_index++) {
        array<long long, 6> child = solve_sum(value / primes[prime_index],
            prime_index + 1);
        for (int type = 0; type < 6; type++) {
            answer[type] = normalize(answer[type] +
                local_values[prime_index][0][type] * child[type]);
        }

        long long power = (long long)primes[prime_index] * primes[prime_index];
        int exponent = 1;
        while (power <= value) {
            child = solve_sum(value / power, prime_index + 1);
            for (int type = 0; type < 6; type++) {
                answer[type] = normalize(answer[type] +
                    local_values[prime_index][exponent][type] *
                    normalize(child[type] + 1));
            }
            exponent++;
            if (power > value / primes[prime_index]) break;
            power *= primes[prime_index];
        }
    }
    memo[key] = answer;
    return answer;
}

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

    int operation;
    cin >> operation >> limit_n;
    int root = (int)sqrt((long double)limit_n);
    while ((long long)(root + 1) * (root + 1) <= limit_n) root++;
    while ((long long)root * root > limit_n) root--;

    vector<bool> composite(root + 1, false);
    for (int i = 2; i <= root; i++) {
        if (composite[i]) continue;
        primes.push_back(i);
        if ((long long)i * i <= root) {
            for (int j = i * i; j <= root; j += i) composite[j] = true;
        }
    }

    quotient_values.reserve(2 * root + 5);
    for (int i = 1; i <= root; i++) {
        quotient_values.push_back(i);
        quotient_values.push_back(limit_n / i);
    }
    sort(quotient_values.begin(), quotient_values.end());
    quotient_values.erase(unique(quotient_values.begin(), quotient_values.end()),
        quotient_values.end());
    small_id.assign(root + 1, -1);
    large_id.assign(root + 1, -1);
    for (int i = 0; i < (int)quotient_values.size(); i++) {
        long long value = quotient_values[i];
        if (value <= root) small_id[value] = i;
        else large_id[limit_n / value] = i;
    }

    prime_sieve_sum.assign(4,
        vector<long long>(quotient_values.size(), 0));
    long long inv2 = 499122177LL;
    long long inv3 = 332748118LL;
    for (int i = 0; i < (int)quotient_values.size(); i++) {
        long long value = quotient_values[i] % MOD;
        long long sum1 = value * ((quotient_values[i] + 1) % MOD) % MOD * inv2 % MOD;
        long long sum2 = sum1 * ((2 * value + 1) % MOD) % MOD * inv3 % MOD;
        long long sum3 = sum1 * sum1 % MOD;
        prime_sieve_sum[0][i] = normalize(quotient_values[i] - 1);
        prime_sieve_sum[1][i] = normalize(sum1 - 1);
        prime_sieve_sum[2][i] = normalize(sum2 - 1);
        prime_sieve_sum[3][i] = normalize(sum3 - 1);
    }

    long long before[4] = {0, 0, 0, 0};
    for (int pi = 0; pi < (int)primes.size(); pi++) {
        int p = primes[pi];
        if ((long long)p * p > limit_n) break;
        for (int i = (int)quotient_values.size() - 1; i >= 0; i--) {
            long long value = quotient_values[i];
            if (value < (long long)p * p) continue;
            int other = quotient_id(value / p);
            long long powers[4] = {1, p % MOD,
                1LL * p * p % MOD, 1LL * p * p % MOD * p % MOD};
            for (int type = 0; type < 4; type++) {
                long long delta = normalize(prime_sieve_sum[type][other] - before[type]);
                prime_sieve_sum[type][i] = normalize(
                    prime_sieve_sum[type][i] - powers[type] * delta);
            }
        }
        long long powers[4] = {1, p % MOD,
            1LL * p * p % MOD, 1LL * p * p % MOD * p % MOD};
        for (int type = 0; type < 4; type++) {
            before[type] = normalize(before[type] + powers[type]);
        }
    }

    prime_prefix.resize(primes.size() + 1);
    prime_prefix[0].fill(0);
    local_values.resize(primes.size());
    for (int pi = 0; pi < (int)primes.size(); pi++) {
        int p = primes[pi];
        long long power = 1;
        int max_exponent = 0;
        while (power <= limit_n / p) {
            power *= p;
            max_exponent++;
        }
        local_values[pi].resize(max_exponent);
        for (int exponent = 1; exponent <= max_exponent; exponent++) {
            int max_power = 3 * exponent;
            vector<long long> powers(max_power + 1, 1);
            for (int i = 1; i <= max_power; i++) {
                powers[i] = powers[i - 1] * (p % MOD) % MOD;
            }
            array<long long, 6> local{};
            for (int x = -exponent; x <= exponent; x++) {
                for (int y = -exponent; y <= exponent; y++) {
                    if (x + y <= exponent) {
                        local[0] = normalize(local[0] + powers[exponent - x - y]);
                    }
                }
            }
            for (int y = -exponent; y <= exponent; y++) {
                local[1] = normalize(local[1] + powers[exponent - y]);
            }
            for (int x = -exponent; x <= exponent; x++) {
                if (2 * x <= exponent) {
                    local[2] = normalize(local[2] + powers[exponent - 2 * x]);
                }
                local[3] = normalize(local[3] + powers[exponent]);
            }
            for (int x = -exponent; x <= exponent; x++) {
                int y = -2 * x;
                if (y >= -exponent && y <= exponent && x + y <= exponent) {
                    local[4] = normalize(local[4] + powers[exponent - x - y]);
                }
            }
            local[5] = powers[exponent];
            local_values[pi][exponent - 1] = local;
        }
        prime_prefix[pi + 1] = prime_prefix[pi];
        for (int type = 0; type < 6; type++) {
            prime_prefix[pi + 1][type] = normalize(
                prime_prefix[pi + 1][type] + local_values[pi][0][type]);
        }
    }

    memo.reserve(3000000);
    array<long long, 6> result = solve_sum(limit_n, 0);
    for (int type = 0; type < 6; type++) result[type] = normalize(result[type] + 1);
    long long perfect = normalize(result[0] - 2 * result[1] - result[2] -
        result[3] - 2 * result[4] + 5 * result[5]);
    cout << (operation == 0 ? result[0] : perfect) << '\n';
    return 0;
}

复杂度

整除分块状态为 $O(\sqrt n)$ ，Min_25 预处理 $O(\sqrt n)$ ，递归求值状态数级别，空间复杂度为整除分块状态数，可支持 $n \le 10^{10}$ 。

总结

加强版的关键在于不枚举大小，而是把答案改写成少量乘法函数前缀和的组合。数学推导与基础版完全一致，算法层面只靠整除分块和 Min_25 筛把上界撑大。

根据不同做法，我们设置了加强版，仅修改了 $n$ 的范围上限。

时间限制： 5.0 秒

空间限制： 1024 MB

题目背景

小 C 在西西艾弗大学担任研究员。今天他遇到了一个优美的数阵，并让作为助手的你来帮他做一些计算。

题目描述

小 C 将这个数阵称为 C 形阵。数阵的数 $\left(A,B,C,D,E,F,G\right)$ 满足如下几条性质：

$A,B,C,D,E,F,G$ 都是正整数
$\frac{A}{B}=\frac{B}{C}$
$\frac{E}{F}=\frac{F}{G}$
$A \times B \times C=C \times D \times E=E \times F \times G$

并按下图所示放置于 C 形阵中：

小 C 定义这个 C 形阵的大小为 $B$ ，价值为 $D$ 。

若这个 C 形阵满足集合 $\{A,B,C,D,E,F,G\}$ 中恰有 6 个互不相同的元素，即 $|\{A,B,C,D,E,F,G\}|=6$ ，则称这个 C 形阵为完美的 C 形阵。以上图两个 C 形阵为例，C 形阵一不是一个完美的 C 形阵，C 形阵二是一个完美的 C 形阵。小 C 并不是个追求完美的人，因此他会通过掷硬币决定是否研究完美的 C 形阵。

具体地，小 C 会给你两个整数 $op,n$ ，若 $op=0$ ，你需要求出所有大小不超过 $n$ 的 C 形阵价值总和；若 $op=1$ ，你需要求出所有大小不超过 $n$ 的完美的 C 形阵价值总和。答案需要对 $998244353$ 取模。

输入格式

从标准输入读入数据。

输入仅有一行，包含两个整数 $op,n$ ，其含义同题目描述。

输出格式

输出到标准输出。

输出一个正整数，表示题目要求的价值总和。

input1

10 2

output1

样例 1 解释

方案	$A$	$B$	$C$	$D$	$E$	$F$	$G$
1	1	1	1	1	1	1	1
2	1	2	4	1	2	2	2
3	1	2	4	2	1	2	4
4	2	2	2	1	4	2	1
5	2	2	2	2	2	2	2
6	2	2	2	4	1	2	4
7	4	2	1	2	4	2	1
8	4	2	1	4	2	2	2
9	4	2	1	8	1	2	4

表格列举了所有符合条件的 C 形阵，总价值为 $25$ 。

input2

11 4

output2

样例 2 解释

下面列举了所有符合条件的 C 形阵，总价值为 $32+32=64$ 。

子任务

全部测试数据满足： $op \in \{0,1\}$ 且 $1 \le n\le 10^{10}$ 。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$op\in$	$n\le$
1	20	$\{0\}$	$10^8$
2	20	$\{0,1\}$	$10^8$
3	30	$\{0\}$	$10^{10}$
4	30	$\{0,1\}$	$10^{10}$

方案	$A$	$B$	$C$	$D$	$E$	$F$	$G$
1	1	1	1	1	1	1	1
2	1	2	4	1	2	2	2
3	1	2	4	2	1	2	4
4	2	2	2	1	4	2	1
5	2	2	2	2	2	2	2
6	2	2	2	4	1	2	4
7	4	2	1	2	4	2	1
8	4	2	1	4	2	2	2
9	4	2	1	8	1	2	4

方案	$A$	$B$	$C$	$D$	$E$	$F$	$G$
1	1	1	1	1	1	1	1
2	1	2	4	1	2	2	2
3	1	2	4	2	1	2	4
4	2	2	2	1	4	2	1
5	2	2	2	2	2	2	2
6	2	2	2	4	1	2	4
7	4	2	1	2	4	2	1
8	4	2	1	4	2	2	2
9	4	2	1	8	1	2	4