「JZOI-1」红包

ID: 6318

远端评测题

2500ms

128MiB

难度: 6

上传者:

标签>

素数判断,质数,筛法

最大公约数,gcd

莫比乌斯反演

二项式定理

容斥

题目背景

新年到了，小僖收到了叔叔寄给他的红包，这个红包里面有很多很多的钱。

小僖收到的红包总额是这样的：

所有 $K$ 元组满足每个元素都是正整数且 $\le N$ ，总额就是这些 $K$ 元组的最小公倍数的乘积。

但由于叔叔并没有那么多的钱，所以结果还要对 $998244353$ 取模。

小僖花了 $10^{-16}$ 秒就算了出来，但他想验证一下是否正确，于是找上了你（别问我为什么他不直接拆开红包看）。

换句话讲，题目只需要你求：

\prod_{i_1=1}^N\prod_{i_2=1}^N...\prod_{i_K=1}^N{\rm lcm}(i_1,i_2...i_K)\mod 998244353

保证 $K>1$ ，其中， ${\rm lcm}(i_1,i_2...i_K)$ ，表示 $i_1,i_2...i_K$ 的最小公倍数。

本题有多组数据。

第一行一个数： $T$ ，表示数据组数。

接下来 $T$ 行，每行两个数， $N,K$ ，表示每组询问。

$T$ 行，每行一个数，表示答案，记得对 $998244353$ 取模。

2
2 2
3 2

8
7776

对于样例的第一组数据，题目要求求出 ${\rm lcm}(1,1)\times {\rm lcm}(1,2)\times {\rm lcm}(2,1)\times {\rm lcm}(2,2)$ 。

显然，除了 ${\rm lcm}(1,1)=1$ 以外其它的结果都为 $2$ ，所以答案为 $1\times2\times2\times2=8$ 。

数据编号	$N\le$	$K\leq$	$T=$
0	$10$	$5$	$10$
1	$10^6$	$2$	$10^3$
2	$10^6$	$3$	$10^3$
3	$100$	$10^{18}$	$100$
4	$10^5$	$100$	$10^3$
5		$3\times10^8$	$1$
6		$10^{100}$	$10$
7	$10^6$	$10^{18}$	$10^3$
8		$10^{100}$
9		$10^{100}$

出题人：你真以为有这么多钱，哈哈，里面装的全是津巴布韦币哦！