CF915G

题目链接

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}\) 取值不同的点有哪些。

code

参考代码：Submission #222532210 - Codeforces