3736. 数学题

“飞机已经降落虹桥机场，还将滑行一段时间，请保持安全带的状态。欢迎您再次乘坐东方航空公司的班机，下次旅途再见。”

飞机还在跑道上滑行，到航站楼还有不少距离。Cuber QQ 开始思考他在银川没有做出来的题目。

题目是这样的：统计 $k$ 元组个数 $(a_1, …, a_k), 1 \le a_i \le n$ 使得 $gcd(a_1, … , a_k, n) = 1$。

显然当 $k=1$ 时，答案就是欧拉函数。

Cuber QQ 为了方便解答，定义 $f(n,k)$ 为满足要求的 $k$ 元组个数，现在需要求出 $\sum\limits_{i=1}^{n}f(i,k)$，由于结果可能很大，所以需要对 $998~244~353$ 取模。

Cuber QQ 打算在下飞机前思考出来。但好像还是不会。