quanjun - 博客园

2026年5月18日

摘要：解决本题的核心在于利用莫比乌斯反演或容斥原理，将“最大公约数（\(\gcd\)）等于 1”的限制转化为“统计倍数个数”。核心思路直接统计 \(\gcd(a_i, a_j, a_k, a_l) = 1\) 的四元组非常困难，因此我们采用莫比乌斯反演进行转化：根据莫比乌斯函数的性质：\(\sum_ 阅读全文

posted @ 2026-05-18 19:09 quanjun 阅读(14) 评论(0) 推荐(0)

洛谷P4213 【模板】杜教筛

摘要：题目链接：https://www.luogu.com.cn/problem/P4213 第一步：理解杜教筛的核心公式杜教筛的本质是：利用狄利克雷卷积来构造一个递推式，通过“数论分块”和“记忆化搜索”来加速前缀和的计算。假设我们要求一个积性函数 \(f\) 的前缀和 \(S(n) = \sum\l 阅读全文

posted @ 2026-05-18 17:36 quanjun 阅读(8) 评论(0) 推荐(0)

洛谷P5495 【模板】Dirichlet 前缀和题解高维前缀和

摘要：题目链接：https://www.luogu.com.cn/problem/P5495 模型转化：题目要求计算 \(b_k = \sum_{i|k} a_i\)。任何正整数都可以唯一分解为质因子的乘积：\(i = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_m^{ 阅读全文

posted @ 2026-05-18 15:24 quanjun 阅读(6) 评论(0) 推荐(0)

HDU5628 Clarke and math 题解狄利克雷卷积+快速幂

摘要：题目链接：https://acm.hdu.edu.cn/showproblem.php?pid=5628 题目大意：输入 \(n\) 和 \(k\)，对于每个 \(i(1 \le i \le n)\)，求 \[f(i) = \sum_{i_1 \mid i} \sum_{i_2 \mid i_1} 阅读全文

posted @ 2026-05-18 14:45 quanjun 阅读(5) 评论(0) 推荐(0)

2026年5月15日

P6210 「SWTR-4」Easy Math Problems 莫比乌斯反演（不完整.没推完）

摘要：没推完，以后再补充…… 题目链接：https://www.luogu.com.cn/problem/P6210 定义 \(g(n, m, c)\) 表示 \([1, m]\) 中存在多少个整数 \(i\) 满足 \(\gcd(i, n) \le c\)。则第二问的答案为 \(g(n, r, c) 阅读全文

posted @ 2026-05-15 19:04 quanjun 阅读(6) 评论(0) 推荐(0)

2026年5月13日

洛谷P3911 最小公倍数之和题解莫比乌斯反演

摘要：题目链接：https://www.luogu.com.cn/problem/P3911 题目大意：给你一个长度为 \(N\) 的数列 \(A_1, A_2, \ldots, A_N\)，求 \[\sum_{i=1}^N \sum_{j=1}^N \operatorname{lcm}(A_i, A_ 阅读全文

posted @ 2026-05-13 09:22 quanjun 阅读(6) 评论(0) 推荐(0)

2026年5月12日

莫比乌斯反演的2+1种形式

摘要：莫比乌斯函数 \(\mu(n)\) 这是反演的核心工具，它的定义如下： \(\mu(1) = 1\) \(\mu(n) = (-1)^k\)：如果 \(n\) 是 \(k\) 个互不相同的质数的乘积。 \(\mu(n) = 0\)：如果 \(n\) 含有平方因子（即某个质因子的平方能整除 \(n\) 阅读全文

posted @ 2026-05-12 15:21 quanjun 阅读(6) 评论(0) 推荐(0)

2026年5月11日

欧拉函数

摘要：欧拉函数（Euler's totient function），通常用希腊字母 \(\varphi(n)\) 表示，是数论中一个非常重要的函数。核心定义对于正整数 \(n\)，欧拉函数 \(\varphi(n)\) 是指：在小于或等于 \(n\) 的正整数中，与 \(n\) 互质（最大公约数为 1 阅读全文

posted @ 2026-05-11 18:03 quanjun 阅读(14) 评论(0) 推荐(0)

2026年5月10日

洛谷P11175 【模板】基于值域预处理的快速离散对数

摘要：题目链接：https://www.luogu.com.cn/problem/P11175 解题思路完全来自 oi.wiki 示例程序： #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int fadd(i 阅读全文

posted @ 2026-05-10 10:16 quanjun 阅读(7) 评论(0) 推荐(0)

2026年5月8日

LOJ143. 质数判定题解 Miller–Rabin 素性测试

摘要：题目链接：https://loj.ac/p/143 解题思路：完全来自 oi.wiki 时间复杂度：\(O(k \log^3 n)\)。 Miller–Rabin 素性测试的结论对于一个奇数 \(n\)，将 \(n - 1\) 表示为 \[n - 1 = 2^s \cdot d \]其中，\(d 阅读全文

posted @ 2026-05-08 18:06 quanjun 阅读(6) 评论(0) 推荐(0)

公告