本文共 1027 字，大约阅读时间需要 3 分钟。

整除分块问题

问题描述

给定一个正整数 ( n )，计算从 1 到 ( n ) 的每个整数 ( i ) 的下取整 ( \left\lfloor \frac{n}{i} \right\rfloor ) 的累加和，并将结果对 998244353 取模。

解题思路

将 ( n ) 整除的结果分成若干块，每一块中的整除结果相同。对于每个块，利用块内元素的数量乘以该块整除结果，累加计算总和。具体步骤包括：

• 遍历从 1 到 ( n ) 的每个可能的区间起始值 ( L )。
• 对于每个 ( L )，确定块的终止值 ( R ) 为 ( \left\lfloor \frac{n}{L} \right\rfloor )。
• 计算该块内所有元素的个数乘以对应的整除结果，累加到最终答案中。

解决代码

class Solution {
public:
    int work(long long n) {
        const long long mod = 998244353;
        long long ans = 0;
        for (long long l = 1; l <= n; ++l) {
            long long r = n / l;
            ans = (ans + (r - l + 1) * (n / l)) % mod;
        }
        return ans;
    }
};

treeI问题

问题描述

给定一棵完全二叉树的 BFS 抄录序列 ( a_i )，恢复二叉树的结构，并利用异或运算对结果进行加密。加密规则如图所示，具体包括每条边的加密方法。

解题思路

通过 BFS 遍历序列 ( a_i ) 从第二个结点开始，逐个计算每个结点与其父节点之间的异或结果，并累加所有异或结果，得到最终加密答案。

解决代码

class Solution {
public:
    long long tree1(std::vector
   
     a) {
        long long ans = 0;
        for (int i = 2; i <= a.size(); ++i) {
            ans += a[i - 1] ^ a[i / 2 - 1];
        }
        return ans;
    }
};