大家好，我是搬题人闲人，这里，来讲一下这道题的正解

题目描述

略

难点

这道题我和三强讨论过后决定评一个 提高加/省选 的难度，因为此题的思维很重要，想明白了，一下就好了，想不明白就死活做不出来。

1. 首先是关于 $f(x)$ 的求法，为什么 $f(x) = x$ 可能好多人没有想懂，知道了也只是在打标时无意发现的（我是不会告诉你我就是这样做对的）。所以我在这里讲一下证明：
   我们先来看 $numgcd(x)$ 这个函数根据题目中的定义我们不难发现这其实是欧拉函数 $\varphi(x)$ ，那么根据 $\varphi(x)$ 的性质我们可以知道两条性质：
   1： $1 \sim x$ 中与 $x$ 的最大公约数为 1 的所有数的和等于 $x \cdot \varphi(x) / 2$
   2： 若 $\varphi(a)$ 与 $\varphi(b)$ 互质，则 $\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)$
   显然，这一道题我们要用到的是第一条性质。
   证明：
   $ \because gcd(a, b) = gcd(a, a - b)$
   $ \therefore $ 与 $a$ 不互质的数 $b$ 和 $a - b$ 成对出现，平均值为 $n / 2$
   故性质一成立。
   证毕。
   由此可以知道 $sumgcd(x) = x \cdot \varphi(x) / 2$
   又$\because f(x) = \frac{2 \cdot sumgcd(x)}{numgcd(x)}$
   $\therefore f(x) = \frac{2 \cdot x \cdot \varphi(x) / 2}{\varphi(x)} = x$
2. 在解决了 $f(x)$ 的问题之后，我们还要考虑如何快速的求出 $\sum_{i = 1}^{n}f(i)^k$ 的值。这里我介绍一种泛用性较高的，也是做简单的方法，我们找出所有询问当中最大的一个 $n$ ，在计算这一组数据时就沿路记录其他的解的值，最后统一输出就可以了。

最后附上代码：

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define  ll long long
#define reg register

using namespace std;

const int N = 1000100, MOD = 998244353;

ll T, k, n[N];
ll ans[N];

inline ll quick_power(ll a)
{
   ll r = 1, base = a;
   ll x = k;
   while (x != 0){
   	if (x & 1 == 1)
       {
   		r *= base;
   		r %= MOD;	
   	}
   	base *= base;
   	base %= MOD;	
   	x = x >> 1;
   } 
   return r % MOD;
}


int main()
{
   cin >>  T >> k;
   ll Max = 0;
   for (reg int i = 1; i <= T; i++)
   {
       scanf("%d", &n[i]);
       if(Max < n[i])
       {
           for (reg int j = Max + 1; j <= n[i]; ++j) ans[j] = (ans[j - 1] + quick_power(j)) % MOD;
           Max = n[i];
       }
       printf("%d\n", ans[n[i]]);
   }
   return 0;
}