题目链接
题目要求一个(1)~(n)的序列的等比子序列个数，多组询问。
单纯枚举公比显然不可行，因为题目并没有限制公比为整数，因此只能考虑构造一波。
显然，长度小于等于2的可以直接(O(1))套公式算。
考虑大于2的。
首先构造一下，设公比 (frac{a}{b} (a > b,gcd(a,b)=1))，首项是 (A)，长度为 (k)，那么这些量就可以唯一确定一个等比数列。容易发现，这个等比数列的末项 (x=Afrac{a^{k-1}}{b^{k-1}})，为保证 (x) 为整数，则必然满足 (b^{k-1} | A)，从而可知 (x) 有因子(a^{k-1})。
综上所述，约束条件如下：
- (a > b,gcd(a,b)=1)
- 末项 (x) 有因子(a^{k-1})
- (k geq 3)
满足以上3个条件，就可以确定一个符合题意的等比子序列。
然后参考题解可以得到下面的式子：
[ans = sum_{a=2}^n varphi(a) lfloor frac{n}{a^{k-1}}
floor
]
当(k=3)时，显然 (lfloor frac{n}{a^2} floor) 只有 (sqrt[3]{n}) 个，复杂度符合题意。
当(k > 3)时，暴力往下展开，一次展开的复杂度为 (O(n^{frac{5}{12}})) 这什么鬼东西啊
暴力展开代码：
for(ll a = 2;a * a <= n;a = r + 1)
{
r = sqrt(n / (n / a / a));
ans += dfs(r) - dfs（a - 1)*(n / a / a) //取模省略便于阅读
}