定义整数 i 的“3 余因子”为 i 最大的无法被 3 整除的因子，记作 md3(i)，例如 md3(3)=1,md3(18)=2,md3(4)=4。请你设计一个高效算法，计算一个正整数区间 [A,B],(0<A<B) 内所有数的“3 余因子”之和，即 ∑i=ABmd3(i)，并分析该算法的时间复杂度。例如，区间 [3,6]的计算结果为 1+4+5+2=12。
这个题我做的不好，我原来的解法是暴力解法，时间复杂度较高。
真正巧妙的办法是使用分治法。区间 [A,B] 中每一个数的“3余因子”显然是相互独立的，因此 ∑i=ABmd3(i)=∑i=1Bmd3(i)−∑i=1A−1md3(i)，原问题被简化为考虑如何对于非负整数 N，求解 ∑i=1Nmd3(i)。
当 N 取 0 时，这个式子是没有意义的所以答案直接取 0。首先考虑区间中无法被 3 整除的数字，例如对 3 取模为 1 或者 2 的数，这些数满足 md3(i)=i，所以可以直接利用等差数列的公式求解。
然后考虑区间 [1,N] 内 3 的倍数，因为区间是从 1 为起点连续不断的，所以 [1,N] 中 3 的倍数一定可以写为 [3∗1,3∗2,⋯,3∗⌊3N⌋] 因子 3 都不能被算上，所以相当于求区间 [1,⌊3N⌋] 中的“3 余因子和”，那么原问题被转化为了一个规模只有原来 1/3 的问题，可以使用分治法。
对 3 取模为 1 或 2 的数字 i 直接计算 md3(i) 的时候，可以选择分类讨论，也可选择直接计算，减取正好被 3 整除的数的和。
相关资源：
