前言

题目链接：洛谷

题目链接：CodeForces

题意

给定 \(n\) 个数 \(a_1\) ~ \(a_n\) ，与 \(k\) 。问有多少个区间 \([l,r]\) 的积能被 \(k\) 整除。

两个区间不同当且仅当 \(l\) 不同或 \(r\) 不同。

思路

可以枚举左端点，然后去找满足条件的右端点。

首先将 \(k\) 分解质因数。

可以发现， \(a_i\) 分解质因数后，只有和有 \(k\) 相同的质因数才有用，否则对于答案是没有贡献的。那么就可以将有用的质因数给用桶给统计起来。

再将这些桶进行前缀和。可以在 \(O(\log n)\) 的时间复杂度内求出所有的对整除影响的质数有多少。

在这个区间内，若对于每个质数的个数均大于 \(k\) 分解后对应质数的个数，则代表这个区间可以整数 \(k\) 。

那么只要枚举左区间，都可以二分出右区间。

因为一个数 \(b\) 最多只有 \(\log b\) 个质因子，所以总的时间复杂度为 \(O(n\log n\log k+\sqrt k)\)

Code

#include