description
求满足长度为 \(n\)，所有项都是 \([l,r]\) 间的正整数且公比为非 1 有理数的等比数列的数量。
\(n\leq 10^7,1\leq l\leq r\leq 10^7\)
solution
先不考虑公比不能为 1 的限制，对于 \([l,r]\) 间的正整数 \(a,b\)，它们可以分别作为首项末项构成等比数列的一个必要条件是 \(\sqrt[n-1]{\dfrac{a}{b}} \in \mathbb{Q}\)。 下面来说明这个条件也是充分的。
设 \(\sqrt[n-1]{\dfrac{a}{b}}=\dfrac{q}{p},(\gcd(p,q)=1)\)，那么这个等比数列的每一项分别是 \(a,a\times \dfrac{q}{p},a\times(\dfrac{q}{p})^2,\dots,a\times(\dfrac{q}{p})^{n-1}=b\)。由于 \(b\in \mathbb{Z}\)，所以 \(p^{n-1}\mid aq^{n-1}\)，又因为 \(\gcd(p,q)=1\)，所以 \(p^{n-1}\mid a\)。进一步，\(p^{i}\mid a,0\leq i\leq n-1\)。所以这个数列的每一项都是整数。又因为等比数列的数值具有单调性，\(a,b\) 都是 \([l,r]\) 间的整数，所以这个数列的每一项都也是 \([l,r]\) 之间的整数。
下面，我们只要统计 \((a,b)\) 满足 \(\sqrt[n-1]{\dfrac{a}{b}} \in \mathbb{Q}\) 的数量即可。
设 \(a,b\) 的质因子分解分别为 \(a=p_{1}^{\alpha_1}p_{2}^{\alpha_2}\dots ,b=p_{1}^{\beta_2}p_{1}^{\beta_2}\dots\)，那么需要满足 \(\forall i\in \mathbb{N},\alpha_i \equiv \beta_i \pmod {n-1}\)。设 \(g(a)=p_{1}^{\alpha_1 \bmod (n-1)}p_{2}^{\alpha_2 \bmod (n-1)}\dots\)，需要 \(g(a)=g(b)\)。
我们只需要计算每种 \(g\) 取值的配对方案数即可。最后还要减去公比为 1 的等比数列的数量 \(r-l+1\) 即可。
综上，设 \(cnt_x =\sum\limits_{i=l}^r [g(i)==x]\)，答案即为 \((\sum\limits_{i=l}^r cnt_{g(i)}) -(r-l+1)\)。
hint
可以用埃氏筛处理出 \(g\) 值，复杂度不超过 \(O(r\log r)\)，实际测试复杂度和 \(O(r\log\log r)\) 相当（设 \(w(i)\) 为 \(i\) 的质因子指数之和，则计算 \(g\) 值的复杂度就是 \(O(\sum w(i))\)）。
code
参考代码：Submission #222571926 - Codeforces
标签：mathbb,dots,等比数列,dfrac,leq,alpha,CF758F From： https://www.cnblogs.com/FreshOrange/p/17690894.html