标签 杜教筛 下的文章
【题解】[NOI2016] 循环之美
[NOI2016] 循环之美
给定 $x,y,k$。
求分数 $\dfrac{x}{y}$ 的个数满足：$1\le x\le n,1\le y\le m,\gcd(x,y)=1$，且在 $k$ 进制下 $\dfrac{x}{y}$ 是纯循环小数（或者整数）。
$1\le n\le 10^9,\ 1\le m\le 10^9,\ 1\le k\le 2\times 10^3$。
给定 $x,y,k$。
求分数 $\dfrac{x}{y}$ 的个数满足：$1\le x\le n,1\le y\le m,\gcd(x,y)=1$，且在 $k$ 进制下 $\dfrac{x}{y}$ 是纯循环小数（或者整数）。
$1\le n\le 10^9,\ 1\le m\le 10^9,\ 1\le k\le 2\times 10^3$。