会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
核心思路：答案一定来自某对下标 (i,j)（允许 i=j）对应的乘积 ai⋅aj 的正约数个数。n≤1000，可枚举全部 n2 对。为了快速求 a⋅b 的约数个数，先对每个 ai 做质因数分解，再把两数的指数对应相加，用公式 ∏(ek+1) 计算。
实现方法：对每个 ai 试除分解得到指数表；枚举所有有序对（含同下标），合并两张指数表并更新答案。同下标时相当于把指数翻倍，对应 ai2。
复杂度分析
设 A=maxai。预处理分解为 O(nA)，枚举合并在指数个数很少时接近 O(n2)。空间 O(nlogA) 量级存放因子。
