单点时限: 4.0 sec
内存限制: 256 MB
“飞机已经降落虹桥机场,还将滑行一段时间,请保持安全带的状态。欢迎您再次乘坐东方航空公司的班机,下次旅途再见。”
飞机还在跑道上滑行,到航站楼还有不少距离。Cuber QQ 开始思考他在银川没有做出来的题目。
题目是这样的:统计 k 元组个数 (a1,…,ak),1≤ai≤n 使得 gcd(a1,…,ak,n)=1。
显然当 k=1 时,答案就是欧拉函数。
Cuber QQ 为了方便解答,定义 f(n,k) 为满足要求的 k 元组个数,现在需要求出 ∑i=1nf(i,k),由于结果可能很大,所以需要对 998 244 353 取模。
Cuber QQ 打算在下飞机前思考出来。但好像还是不会。
输入数据只有一行,包含两个函数 n,k(1≤n≤109,1≤k≤1000) 。
输出只包含一行,表示求和的结果。
4 2
24