区间[L,R]强加密密钥对计数算法优化求助

核心思路梳理 #

强密钥对的条件可转化为：

• x < y
• x、y均为无平方因子数（即题目中的「特殊数」）
• x与y互质（因为x*y为无平方因子数等价于x、y无公共质因子）

利用输入约束R-L ≤ 1000的特性，我们可以通过筛法快速标记特殊数+互质对数统计的组合方案大幅提升效率。

步骤1：快速筛选区间内的特殊数 #

替代逐个质因数分解的低效方法，我们通过枚举所有平方数k²（k≥2），标记区间内能被其整除的数，剩余未被标记的即为特殊数：

1. 创建长度为R-L+1的布尔数组is_special，初始值全为True。
2. 枚举k从2到√R（计算为int(math.isqrt(R))）：
   • 计算平方数k_sq = k * k
   • 找到区间内第一个能被k_sq整除的数：start = ((L + k_sq - 1) // k_sq) * k_sq
   • 从start开始，以k_sq为步长遍历区间，将对应位置的is_special[start - L]设为False。
3. 遍历is_special数组，收集所有L+i（其中is_special[i]为True）到列表S中，S即为区间内所有特殊数。

此方法的时间复杂度为O(√R + R-L)，远快于逐个质因数分解大数的方案。

步骤2：统计符合条件的强密钥对 #

在特殊数列表S中，统计所有x < y且gcd(x,y)=1的数对：

1. 初始化答案ans = 0。
2. 遍历列表S的每个元素S[i]（i从0到len(S)-2）：
   • 遍历S[j]（j从i+1到len(S)-1）：
     • 若gcd(S[i], S[j]) == 1，则ans += 1。
3. 最终ans即为强密钥对的数量。

由于len(S)最多为1000，双重循环仅需约5e5次操作，且gcd运算为硬件优化的高效操作，整体耗时极短。

示例验证（输入L=3, R=9） #

1. 筛选特殊数：标记4（2²）、8（2²）、9（3²），剩余特殊数为[3,5,6,7]。
2. 统计互质对数：
   • (3,5)、(3,7)、(5,6)、(5,7)、(6,7)，共5组，与示例输出一致。

内容的提问来源于stack exchange，提问作者InsiderLabs