description
给定序列 ({a})，现需要从中选择非空子集 (S) 与不属于 (S) 的元素 (x)，满足 (gcd(x,S)=1,gcd(S) eq 1)，求方案数。
solution
省去推式子的过程，得到答案为 (summu(d) imes (s_d - n) imes (2^{s_d}-1))，其中 (s_d) 表示 (d) 的倍数个数。
枚举 (d) 的倍数计算 (s_d) 可以做到 (O(Aln A))（调和级数），在 (Aleq 10^7) 的时候比较危（虽然有人过了）。
如果把质数当作维数，根据唯一分解式可以确定所有正整数的高维坐标。做个类似高维前缀和即可。
时间复杂度类似于埃氏筛，为 (O(Alnln A))。
submission
details
关于时间复杂度为什么是 (O(Aln ln A)) 而不是 (O(frac{A}{ln A} imes ln A) = O(A))（虽然两者实际运行差别不大），直观来说就是素数分布并不是均匀的，严格证明我也不会。