[CmdOI2019] 简单的数论题 - Luogu - 题目详情 - 云斗学院

ID: 4350

远端评测题

1000~2000ms

128MiB

难度: 7

上传者:

标签>

数学

块状链表,块状数组,分块

题目描述

给出 $n,m$ 求下列式子的值：

\sum\limits_{i=1}^n\sum\limits_{j=1}^m \varphi\left(\dfrac{{\rm lcm}(i,j)}{\gcd(i,j)}\right) \bmod 23333

输入格式

第一行一个整数 $T$ ，表示询问数。

后 $T$ 行每行两个整数 $n,m$ ,表示一个询问。

输出格式

对于每个询问，输出一行一个整数，表示答案。

输入数据 1

输出数据 1

输入数据 2

输出数据 2

52
7572
21475

提示

对于所有测试点， $T\leq 3\times 10^4,\ m\leq n\leq 5\times 10^4$ 。

测试点编号	$n,m\leq$	$T$	时限	特殊性质
#1~2	$100$		$\texttt{1s}$
#3~4	$2000$	$3\times 10^4$	$\texttt{1s}$
#5~6	$3\times 10^4$	$5000$	$\texttt{2s}$
#7~8	$5\times 10^4$	$3\times 10^4$		$n=m$
#9~10	$5\times 10^4$	$3\times 10^4$