链接：https://www.luogu.com.cn/problem/P1587
题目描述：求有多少个$\frac{a}{b}(1<=a<=n,1<=b<=m)$在$k$进制下是纯循环小数$(注意:相等的数只算一次)$。
题解：可以发现$\frac{a}{b}(1<=a<=n,1<=b<=m)$在$k$进制下是纯循环小数当且仅当$\frac{a}{b}$化为最简分数后分母与$k$互质。我们可以只在最简分数处算，则原问题化为求$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==1][gcd(j,k)==1]$
$\qquad\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==1][gcd(j,k)==1]$
$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}μ(d)[gcd(j,k)==1]$
$=\sum_{d=1}^{n}μ(d)\lfloor \frac{n}{d}\rfloor\sum_{d|j}[gcd(j,k)==1]$
$=\sum_{d=1}^{n}μ(d)\lfloor \frac{n}{d}\rfloor\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(dj,k)==1]$
$=\sum_{d=1}^{n}μ(d)\lfloor \frac{n}{d}\rfloor [gcd(d,k)==1]\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(j,k)==1]$
令$f(n,k)=\sum_{i=1}^{n}[gcd(i,k)==1],g(n,k)=\sum_{i=1}^{n}μ(i)[gcd(i,k)==1]$
则原式可以用数论分块快速求出，考虑如何快速求出这两个函数，可以利用递归的思想，将$k$推向$k/p$($p$为$k$的一个质因子)。
$f(n,k)=\sum_{i=1}^{n}[gcd(i,k)==1]$
$=\sum_{i=1}^{n}[gcd(i,\frac{k}{p})==1]-\sum_{i=1}^{n}[gcd(i,\frac{k}{p})==1][p|i]$
$=f(n,k/p)-\sum_{i=1}^{n}[gcd(i,\frac{k}{p})==1][p|i]$
$=f(n,k/p)-\sum_{i=1}^{\lfloor \frac{n}{p} \rfloor}[gcd(ip,\frac{k}{p})==1]$
当$k$中含有两个质因子$p$时，该式就等于$f(n,k/p)$。
当$k$中含有一个质因子$p$时
原式$=f(n,k/p)-\sum_{i=1}^{\lfloor \frac{n}{p} \rfloor}[gcd(i,\frac{k}{p})==1]$
$=f(n,k/p)-f(\lfloor \frac{n}{p} \rfloor,k/p)$
$g(n,k)=\sum_{i=1}^{n}μ(i)[gcd(i,k)==1]$
$=\sum_{i=1}^{n}μ(i)[gcd(i,\frac{k}{p})==1]-\sum_{i=1}^{n}μ(i)[gcd(i,\frac{k}{p})==1][p|i]$
$=g(n,k/p)-\sum_{i=1}^{n}μ(i)[gcd(i,\frac{k}{p})==1][p|i]$
$=f(n,k/p)-\sum_{i=1}^{\lfloor \frac{n}{p} \rfloor}μ(ip)[gcd(ip,\frac{k}{p})==1]$
当$k$中含有两个质因子$p$时，该式就等于$g(n,k/p)$。
当$k$中含有一个质因子$p$时
原式$=g(n,k/p)-\sum_{i=1}^{\lfloor \frac{n}{p} \rfloor}μ(i)μ(p)][gcd(i,p)==1][gcd(i,\frac{k}{p})==1]$
$=g(n,k/p)-μ(p)\sum_{i=1}^{\lfloor \frac{n}{p} \rfloor}μ(i)[gcd(i,k)==1]$
$=g(n,k/p)+\sum_{i=1}^{\lfloor \frac{n}{p} \rfloor}μ(i)[gcd(i,k)==1]$
$=g(n,k/p)+g(\lfloor \frac{n}{p} \rfloor,k)$
```
#include