description
\(f_k(x)\) 表示所有长度为 \(x\) ，元素取值范围为 \([1,k]\) 中的整数的序列 \(\{a\}\)，满足 \(\gcd(a_1,a_2,\dots,a_x)=1\) 的序列的个数。
给定 \(n,k\leq 2\times 10^6\)
分别 求出 \(f_1(n),f_2(n),\dots ,f_k(n)\)。
模大质数
3.50 s
256 MiB
solution
推式子得，
\(f_k(n)=\sum\limits_{i=1}^k\mu(i)(\lfloor\dfrac{k}{i}\rfloor)^n\)。
暴力计算是 \(O(\sum\limits^k\sqrt{i})=O(k\sqrt{k})\) 的。
考虑如何优化。
注意到只有 \(i\mid k+1\) 时，\(\lfloor\dfrac{k}{i}\rfloor\) 较 \(\lfloor\dfrac{k+1}{i}\rfloor\) 的值会改变。
于是可以得出递推式 \(f_k(n)=f_{k+1}(n)-\sum\limits_{p\mid k+1}\mu(p)((\lfloor\dfrac{k+1}{p}\rfloor)^n-(\lfloor\dfrac{k}{p}\rfloor)^n)\)
后面的东西可以 \(O(k\log nk)\) 预处理出来。
总共的时间复杂度 \(O(k\log nk)\)
可以过掉本题（有点卡常）。
使用狄利克雷前缀和以及线性筛求自然数 \(n\) 次幂可以把复杂度降到 \(O(k\log\log k)\)。
不过我现在不会狄利克雷前缀和，就没有这样做。
hint
本题需要注意到 \(f_{k}\) 和 \(f_{k+1}\) 取值不同的点有哪些。