lc1819——枚举因数并判定，两种解法

https://leetcode-cn.com/problems/number-of-different-subsequences-gcds/solution/mei-ju-yin-shu-bing-pan-ding-liang-chong-fj6e/
传送门
法一
力扣上大多数题解都是法一。因为值域是2e5，又是和公约数有关，所以肯定会考虑枚举因数。这里就考虑枚举i，并判定是否存在一个子序列的gcd是i。
开桶c[]记录每个数出现次数，枚举i的所有倍数j*i，则sum(c[j*i])就找到了数组里i的倍数构成的集合。对于每个合法j，求它们的gcd。若求得gcd为1，则说明该集合的gcd就是i，则i对答案有1的贡献；否则i对答案无贡献。
时间复杂度O(n*logn*logn)。
法二
这位神犇的解法是法二。定义c[i]为数组中是i的倍数的数字个数。对于i的倍数j*i，j >= 2，因为j*i的倍数的

lc1819——枚举因数并判定，两种解法最先出现在Python成神之路。