求数组中元素相等且索引乘积可被X整除的数对的高效解法

核心优化方向 #

先利用a[i] = a[j]的条件做分组，仅在相同元素对应的下标组内统计合法数对，避免跨组无效计算，再通过数论变形把下标乘积整除的判断复杂度降到常数级，整体可以把时间复杂度压到O(n * d(X))（d(X)为X的约数个数），完全支持1e5规模的输入。

具体实现步骤 #

• 第一步：分组预处理
  遍历数组，用哈希表存储每个元素值对应的所有下标列表，键为元素值，值为下标集合。后续仅需计算每个下标集合内的合法数对，求和即可得到最终结果。
• 第二步：数论条件变形
  条件(i * j) % X == 0等价于：i和j分别与X的最大公约数的乘积是X的倍数，即 (gcd(i,X) * gcd(j,X)) % X == 0。
  原理是i中所有属于X的因子都包含在gcd(i,X)里，剩余部分和X互质，j同理，所以仅需要两个最大公约数的乘积覆盖X的所有因子即可满足乘积整除要求。
• 第三步：单组统计逻辑
  对每个下标集合按从小到大遍历（天然满足i<j的条件），维护一个计数字典cnt，记录已经遍历过的下标对应的gcd(i,X)的出现次数：
  1. 对当前下标j，计算g_j = gcd(j, X)
  2. 遍历所有X的正约数g_i，如果(g_i * g_j) % X == 0，就把cnt.get(g_i, 0)加到总答案中
  3. 更新计数：cnt[g_j] = cnt.get(g_j, 0) + 1
• 可选优化：提前预处理X的所有正约数，并且对每个约数g提前存好满足(g * g') % X ==0的约数g'列表，避免每次遍历所有约数做判断，进一步提升效率。

复杂度说明 #

1e5以内的X最多只有100+个约数，整体运算量在1e7级别，远低于超时阈值。

边界情况处理 #

• 如果X=1，所有i<j的同值数对都合法，直接对每个大小为k的下标组加k*(k-1)/2即可，无需额外遍历。
• 如果下标从0开始，gcd(0, X) = X，上述逻辑依然成立，不需要特殊处理。

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