考虑这种一堆数字(gcd = k)
有经典做法。
考虑设(f(x))为(gcd)是(x)的倍数的方案数。
(g(x))为(gcd)刚好为(x)的方案数。
则有
(f(x) = sum_{x | k}g(k))
莫反一下则对应有
(g(x) = sum_{x | k}mu(frac{k}{x})g(k))
因为我们求的是(g(1))
那么有(g(1) = sum_{x | k}mu(k)f(k))
那么(f(k))显然为([n^{frac{1}{k}} - 1])
考虑这种一堆数字(gcd = k)
有经典做法。
考虑设(f(x))为(gcd)是(x)的倍数的方案数。
(g(x))为(gcd)刚好为(x)的方案数。
则有
(f(x) = sum_{x | k}g(k))
莫反一下则对应有
(g(x) = sum_{x | k}mu(frac{k}{x})g(k))
因为我们求的是(g(1))
那么有(g(1) = sum_{x | k}mu(k)f(k))
那么(f(k))显然为([n^{frac{1}{k}} - 1])