题目
半素数序列
解题思路（线性筛法优化生成）
半素数定义与筛选条件
半素数指两个素数相乘得到的数（含平方形式，如4=2×2）。其核心判定条件为：n是合数，且 n除以最小质因数后结果仍为素数。此条件等价于 n = p × q（其中 p≤q且 p、q均为素数）。
线性筛法基础：素数生成与最小质因数记录
采用欧拉筛（线性筛）在O(n)时间复杂度内生成素数列表，同时记录每个数的最小质因数。筛法关键特性：每个合数仅被其最小质因数筛去一次，确保效率。筛法过程中同步维护 isPrime（素数标记）和 minPrime（最小质因数）数组。
两种高效生成半素数的策略对比
方法一通过双重循环遍历素数列表生成所有 p×q（p≤q），生成后排序。时间复杂度O(π² + n log n)（π为素数个数，10⁶内约8万）。方法二利用 minPrime数组直接判断，仅需O(n)遍历，避免双重循环与排序，效率显著提升。
参考代码
方法一：双重循环生成后排序
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
List<Integer> halfPrimes = seive(1000000); // 生成所有 ≤100万的半素数
while (q-- > 0) {
int index = sc.nextInt();
System.out.println(halfPrimes.get(index - 1)); // 1-indexed 索引
}
}
private static List<Integer> seive(int limit) {
// 初始化素数标记数组（true=素数）
boolean[] isPrime = new boolean[limit + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false; // 0和1非素数
List<Integer> primes = new ArrayList<>(); // 存储素数列表
// 线性筛法生成素数
for (int i = 2; i <= limit; i++) {
if (isPrime[i]) {
primes.add(i); // 添加当前素数
}
// 用已知素数筛合数
for (int prime : primes) {
if (i * prime > limit) break; // 超出上限提前终止
isPrime[i * prime] = false; // 标记为合数
if (i % prime == 0) break; // 保证每个合数仅被最小质因数筛去
}
}
// 生成半素数：p≤q避免重复（如2×3和3×2）
List<Integer> halfPrimes = new ArrayList<>();
for (int i = 0; i < primes.size(); i++) {
int p = primes.get(i);
for (int j = i; j < primes.size(); j++) {
long product = (long) p * primes.get(j); // 防止int溢出
if (product > limit) break; // 超出上限终止内层循环
halfPrimes.add((int) product);
}
}
Collections.sort(halfPrimes); // 生成顺序非升序需排序
return halfPrimes;
}
}
方法二：利用最小质因数直接判断
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
List<Integer> halfPrimes = seive(1000000); // 优化版筛法
while (q-- > 0) {
int index = sc.nextInt();
System.out.println(halfPrimes.get(index - 1)); // 1-indexed 索引
}
}
private static List<Integer> seive(int limit) {
// minPrime[i] = i的最小质因数
int[] minPrime = new int[limit + 1];
boolean[] isPrime = new boolean[limit + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false; // 0和1非素数
List<Integer> primes = new ArrayList<>();
// 线性筛法：同时生成素数列表和最小质因数
for (int i = 2; i <= limit; i++) {
if (isPrime[i]) {
primes.add(i);
minPrime[i] = i; // 质数的最小质因数是自身
}
for (int prime : primes) {
if (i * prime > limit) break;
isPrime[i * prime] = false; // 标记合数
minPrime[i * prime] = prime; // 记录最小质因数
if (i % prime == 0) break; // 保证最小质因数唯一性
}
}
// 直接生成半素数：i是合数且i/minPrime[i]是素数
List<Integer> halfPrimes = new ArrayList<>();
for (int i = 4; i <= limit; i++) {
// 条件解释：i是合数（!isPrime[i]），且i除以最小质因数后仍为素数（isPrime[i/minPrime[i]]）
if (!isPrime[i] && isPrime[i / minPrime[i]]) {
halfPrimes.add(i);
}
}
return halfPrimes;
}
}
蓝桥约数
解题思路
利用约数个数奇偶性的关键观察
一个正整数的约数总是成对出现，因此其约数个数通常为偶数。只有当该数是完全平方数时，其平方根无法配对，导致约数个数为奇数。由此可得：若两个正整数 a 与 b 的约数个数之差为 1（即一奇一偶），则其中必有一个是完全平方数。
这一性质直接限定了蓝桥约数 N = a \times b 的结构：在所有满足 a \cdot b = N 且 |d(a) - d(b)| = 1 的分解中，a 或 b 中必有一个是完全平方数。
枚举完全平方因数进行高效验证
基于上述结论，无需枚举 N 的所有因数对，只需遍历所有不超过 N 的完全平方数 s = k^2，检查 s 是否整除 N。若整除，则令 t = N / s，并验证 |d(s) - d(t)| = 1 是否成立。只要存在一组满足条件的 (s, t)，即可判定 N 为蓝桥约数。
该策略将每数的验证复杂度控制在 O(\sqrt{N})，且常数更小、逻辑更贴合问题本质。
线性筛预处理约数个数
为快速获取任意数的约数个数 d(x)，采用线性筛（欧拉筛）在 O(n) 时间内预处理出 d[1..n]。筛法过程中维护每个数的最小质因子的指数，利用公式：
- 若 p \mid i（p 为最小质因子）：d[i \cdot p] = d[i] \div (e+1) \times (e+2)，其中 e 为 i 中 p 的指数；
- 否则（p \nmid i）：
d[i \cdot p] = d[i] \times 2
从而实现高效递推。（原理见下方详解）
前缀和加速区间查询
题目要求回答多个区间 [l, r] 内蓝桥约数的个数。在预处理出每个数是否为蓝桥约数后，构建前缀和数组，使每次查询可在 O(1) 时间内完成。
线性筛约数个数
为什么这个筛法能正确算出每个数的约数个数？
核心思想：任何一个数都能拆成质因数相乘
比如：
12 = 2² × 3¹18 = 2¹ × 3²7 = 7¹（质数）
而一个数的约数个数，只跟它的质因数指数有关。
✅ 公式（记住这个就行）：
如果
n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ
那么n 的约数个数 = (a₁ + 1) × (a₂ + 1) × … × (aₖ + 1)
例子：
12 = 2² × 3¹→ 约数个数 =(2+1) × (1+1) = 3×2 = 6（约数：1,2,3,4,6,12 ✅）9 = 3²→(2+1) = 3（1,3,9 ✅）
所以问题变成：怎么快速知道每个数的质因数指数？
线性筛的聪明之处：从小到大构造每个数，并记录“最小质因子的指数”
我们用两个数组：
divisorCount[i]：i 的约数个数（最终答案）minExp[i]：i 的最小质因子在它质因数分解中出现的次数（指数）
情况一：i 是质数（没被筛过）
- 比如
i = 5 - 质因数分解：
5¹ - 所以
divisorCount[5] = 1 + 1 = 2 minExp[5] = 1（最小质因子是 5，指数 1）
✅ 直接设：
divisorCount[i] = 2;
minExp[i] = 1;
情况二：用 i 去乘一个质数 p，生成新数 x = i * p
这时候分两种子情况：
✅ 子情况 A：p 整除 i（即 i % p == 0）
这意味着：p 就是 i 的最小质因子（因为我们按从小到大遍历质数）
举个例子：
i = 12 = 2² × 3，最小质因子是 2p = 2（当前质数），x = 12 × 2 = 24 = 2³ × 3
原来 i=12 的最小质因子指数是 minExp[12] = 2（因为 2²）
现在 x=24 的最小质因子指数变成 2 + 1 = 3
那约数个数怎么变？
divisorCount[12] = (2+1)(1+1) = 6divisorCount[24] = (3+1)(1+1) = 8
注意到：只有最小质因子的指数变了，其他不变所以我们可以从 divisorCount[i] 推出来：
新约数个数 = 旧约数个数 ÷ (旧指数 + 1) × (新指数 + 1)
也就是：
minExp[x] = minExp[i] + 1;
divisorCount[x] = divisorCount[i] / (minExp[i] + 1) * (minExp[i] + 2);
然后 break —— 因为之后更大的质数不是 x 的最小质因子，不能这么算了。
✅ 子情况 B：p 不整除 i（即 i % p != 0）
说明：p 是一个全新的质因子，而且比 i 的所有质因子都小（因为 primes 从小到大），所以 p 就是 x = i * p 的最小质因子
例子：
i = 9 = 3²，p = 2（2 不整除 9）x = 18 = 2¹ × 3²
此时：
x的最小质因子是p=2，指数是 1 →minExp[x] = 1- 因为
i和p没有公共质因子（互质），所以：divisorCount[x] = divisorCount[i] × divisorCount[p]- 而
divisorCount[p] = 2（质数） - 所以
divisorCount[x] = divisorCount[i] × 2
✅ 直接写：
minExp[x] = 1;
divisorCount[x] = divisorCount[i] * 2;
总结一句话
这个算法之所以能算对约数个数，是因为：
- 它从小到大构造每个合数；
- 对每个数，只通过它的“最小质因子”来更新；
- 利用“约数个数 = 各质因子指数+1 的乘积”这个公式；
- 分两种情况处理：最小质因子已存在 vs 最小质因子是新的。
只要明白：
“约数个数由质因数指数决定”，以及“线性筛保证每个数只被最小质因子筛一次”。
举个完整流程（n=6）
| num | primes so far | 处理过程 |
|---|---|---|
| 2 | [] → [2] | 质数 → d[2]=2, minExp[2]=1 |
| 3 | [2] → [2,3] | 质数 → d[3]=2, minExp[3]=1 |
| 4 | [2,3] | 2: 2%2==0 → d[4] = d[2]/(1+1)(1+2)=2/23=3, minExp[4]=2 → break |
| 5 | [2,3] → [...,5] | 质数 → d[5]=2 |
| 6 | [...] | 2: 6=3×2, 3%2!=0 → d[6]=d[3]*2=4, minExp[6]=1 3: 3%3==0 → d[9]=...（但 9>6 跳过） |
结果：d[6]=4 ✅（1,2,3,6）
本质就是：利用质因数分解 + 动态更新指数信息。
参考代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
final int MAX_N = 100000;
// 线性筛预处理 1~MAX_N 的约数个数 d[i]
int[] d = sieveDivisorCount(MAX_N);
// 标记每个数是否为蓝桥约数（利用完全平方数性质）
boolean[] isLanQiao = new boolean[MAX_N + 1];
for (int x = 1; x <= MAX_N; x++) {
isLanQiao[x] = isLanQiao(x, d);
}
// 前缀和，支持区间查询
int[] prefix = new int[MAX_N + 1];
for (int i = 1; i <= MAX_N; i++) {
prefix[i] = prefix[i - 1] + (isLanQiao[i] ? 1 : 0);
}
// 处理查询
while (q-- > 0) {
int l = sc.nextInt();
int r = sc.nextInt();
System.out.println(prefix[r] - prefix[l - 1]);
}
}
private static boolean isLanQiao(int x, int[] d) {
// 枚举所有完全平方数 s = k*k <= x
for (int k = 1; (long) k * k <= x; k++) {
int sq = k * k;
if (x % sq == 0) {
int other = x / sq;
if (Math.abs(d[sq] - d[other]) == 1) {
return true;
}
}
}
return false;
}
/**
* 线性筛预处理 1~n 每个数的约数个数
* 返回数组 divisorCount，divisorCount[i] = i 的约数个数
*/
public static int[] sieveDivisorCount(int n) {
// 状态数组
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
List<Integer> primes = new ArrayList<>();
// 结果数组
int[] divisorCount = new int[n + 1]; // divisorCount[i] = i 的约数个数
int[] minPrimeExp = new int[n + 1]; // minPrimeExp[i] = i 的最小质因子的指数
divisorCount[1] = 1;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
primes.add(i);
divisorCount[i] = 2;
minPrimeExp[i] = 1;
}
for (int p : primes) {
if (i * p > n) break;
isPrime[i * p] = false;
if (i % p == 0) {
// p 是 i 的最小质因子（因为 primes 是从小到大）
minPrimeExp[i * p] = minPrimeExp[i] + 1;
// 更新公式：原指数是 e，贡献 (e+1)，新是 (e+2)
divisorCount[i * p] = divisorCount[i] / (minPrimeExp[i] + 1) * (minPrimeExp[i] + 2);
break; // 关键：只被最小质因子筛一次
}
// 此时 p 不整除 i → p 是 nextNum 的最小质因子，且是第一次出现
minPrimeExp[i * p] = 1;
divisorCount[i * p] = divisorCount[i] * 2; // 因为 d(p)=2，且互质
}
}
return divisorCount;
}
}
九面数字墙
解题思路
这道题的本质是求所有排列组成的数字之和。如果我们把成千上万个数字列出来硬算，肯定是不行的。我们需要换个角度，像小学生做加法一样，“竖着”来看这个问题。
核心直觉：竖式加法的奥秘
假设我们要计算几个数的和，比如由数字 1, 1, 2 组成的所有排列：112 + 121 + 211。
我们不要横着加，而是列成竖式看：
1 1 2
1 2 1
+ 2 1 1
-------
你会发现一个惊人的规律：
- 个位这列：2+1+1=4。
- 十位这列：1+2+1=4。
- 百位这列：1+1+2=4。
每一列的数字加起来其实都是一样的！我们记这个和为 “单列和”。
最终的总结果，其实就是：
提取公因数后：
所以，解题只需要两步：
- 算出单列和是多少。
- 算出 N 个 1 组成的全1数是多少。
利用“概率”直觉计算单列和
单列和，就是把所有排列中，出现在某一位（比如个位）上的数字全部加起来。
我们可以利用概率来思考，这比背复杂的组合公式要简单得多。
假设一共有 N 个数字。
-
总共有多少种排列？
这是一个经典的多重集排列问题。如果所有数字都不同，排列数是 N!。但因为有重复的数字（比如 c_1 个 1），我们要除以重复部分的阶乘。
\text{总排列数} = \frac{N!}{c_1! \times c_2! \times \dots \times c_9!} -
数字 i 在个位出现了几次？
想象你闭着眼睛从 N 个数字里随便抽一个放在个位。
-
抽到数字 i 的概率是：\frac{\text{数字 } i \text{ 的个数}}{N}。
-
那么在所有排列中，数字 i 在个位出现的总次数就是：
\text{出现次数} = \text{总排列数} \times \text{抽到 } i \text{ 的概率}\text{出现次数} = \text{总排列数} \times \frac{c_i}{N}
-
-
计算单列和
算出每个数字 1 \sim 9 的出现次数后，乘上它们自己的数值，再加在一起：
\text{单列和} = \sum_{i=1}^9 (\text{数字 } i \text{ 的出现次数} \times i)
构造全1数
我们需要一个由 N 个 1 组成的数（11\dots1）。
这是一个等比数列求和的结果，公式为：
关于取模运算的注意事项
题目要求对 998244353 取模。
- 加法、乘法可以直接取模。
- 除法不能直接做：公式里涉及到的除法（比如除以 N，除以 c_i!，除以 9），在模运算里需要转化为乘以逆元（可以理解为该数在模意义下的倒数）。代码中会使用费马小定理
power(a, MOD-2)来计算逆元。
参考代码
import java.io.*;
import java.util.*;
public class Main {
// 题目要求的模数
static final long MOD = 998244353;
// 数据范围限制，总位数最多 10^5
static final int MAX_N = 100005;
// 预处理数组：fac存储阶乘，invFac存储阶乘的逆元
static long[] fac = new long[MAX_N];
static long[] invFac = new long[MAX_N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 1. 读入数据
int[] count = new int[10]; // count[i] 表示数字 i 有多少个
int N = 0; // N 表示总位数 (所有 c_i 的和)
for (int i = 1; i <= 9; i++) {
if (sc.hasNextInt()) {
count[i] = sc.nextInt();
N += count[i];
}
}
// 特殊情况处理
if (N == 0) {
System.out.println(0);
return;
}
// 2. 预处理阶乘和逆元，为计算排列数做准备
precomputeFactorials();
// 3. 第一步：计算“总排列数”
// 公式：Total = N! / (c1! * c2! * ... * c9!)
// 在代码中，"除以 c_i!" 变成了 "乘以 c_i! 的逆元"
long denominatorInv = 1;
for (int i = 1; i <= 9; i++) {
denominatorInv = (denominatorInv * invFac[count[i]]) % MOD;
}
// 总排列数 = N! * 所有分母阶乘的逆元积
long totalPermutations = (fac[N] * denominatorInv) % MOD;
// 4. 第二步：计算“单列和”
// 即计算任意一列（比如个位）所有数字加起来是多少
long singleColumnSum = 0;
// 计算 N 的逆元，用于概率计算 (概率 = 个数 / N)
long invN = modInverse(N);
for (int i = 1; i <= 9; i++) {
if (count[i] == 0) continue;
// 核心逻辑：利用概率计算数字 i 出现的次数
// 次数 = 总排列数 * (数字 i 的个数 / 总数 N)
// 出现次数 = 总排列数 * (数字 i 个数 / N)
// 写成代码运算顺序：(Total * Count * invN)
long times = totalPermutations;
times = (times * count[i]) % MOD;
times = (times * invN) % MOD;
// 该数字对单列和的贡献 = 次数 * 数字本身的值
long contribution = (times * i) % MOD;
// 累加到单列和
singleColumnSum = (singleColumnSum + contribution) % MOD;
}
// 5. 第三步：计算“全1数”
// 我们需要构造 N 个 1 组成的数：11...1
// 数学公式为 (10^N - 1) / 9
long tenPowN = power(10, N); // 计算 10^N
long allOnes = (tenPowN - 1 + MOD) % MOD; // 分子：10^N - 1 (注意防负数)
long inv9 = modInverse(9); // 分母：9 的逆元
allOnes = (allOnes * inv9) % MOD; // 相当于除以 9
// 6. 最终答案 = 单列和 * 全1数
long ans = (singleColumnSum * allOnes) % MOD;
System.out.println(ans);
}
// --- 下面是数学工具函数 ---
// 预处理阶乘及其逆元
static void precomputeFactorials() {
fac[0] = 1;
for (int i = 1; i < MAX_N; i++) {
fac[i] = (fac[i - 1] * i) % MOD;
}
// 计算 N! 的逆元
invFac[MAX_N - 1] = modInverse(fac[MAX_N - 1]);
// 逆向递推计算前面所有阶乘的逆元
for (int i = MAX_N - 2; i >= 0; i--) {
invFac[i] = (invFac[i + 1] * (i + 1)) % MOD;
}
}
// 快速幂算法：计算 (base^exp) % MOD
static long power(long base, long exp) {
long res = 1;
base %= MOD;
while (exp > 0) {
if ((exp & 1) == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return res;
}
// 求逆元 (相当于求模意义下的倒数)
// 根据费马小定理，a^(MOD-2) 就是 a 的逆元
static long modInverse(long n) {
return power(n, MOD - 2);
}
}
额外知识点：模运算中的“除法”——逆元
在解决取模运算（A \pmod M）的问题中，加法和乘法都很容易处理：
但是，除法却不能直接进行取模操作：
例如：\frac{10}{2} = 5。如果对 8 取模：
但如果先取模再除：
结果错误！
为了在模 M 的世界里实现“除以 B”的操作，我们引入了逆元的概念。
逆元的定义
逆元 \text{inv}(B)，就是指一个数 X，使得它乘以 B 之后，对 M 取模的结果是 1。
如果我们找到了 B 的逆元 \text{inv}(B)，那么在模 M 意义下，“除以 B”就等价于“乘以 \text{inv}(B)”：
如何计算逆元？（费马小定理）
在我们的题目中，模数 M=998244353 是一个质数。当模数 M 是质数时，我们可以使用最简单高效的方法——费马小定理来计算逆元。
费马小定理指出：如果 M 是一个质数，且 B 不是 M 的倍数，那么：
将上式拆开：
对比逆元的定义 B \times X \equiv 1 \pmod M，我们可以得出结论：
B 的逆元 X 就是 B 的 M-2 次方。
\text{inv}(B) \equiv B^{M-2} \pmod M
在代码中，我们通过 快速幂 函数 power(n, MOD - 2) 来高效地计算这个逆元。
总结：
无论是计算总排列数时需要除以阶乘 (c_i!)，还是计算全1数时需要除以 9，我们都没有进行真正的除法，而是通过乘以它们的逆元来巧妙地完成了模意义下的运算。
