[CmdOI2019] 简单的数论题
题目描述
给出 $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
5
10 10
20 20
30 30
40 40
50 50
输出样例 #1
768
13312
16218
7160
9031输入样例 #2
3
5 4
20 15
100 88输出样例 #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$ | $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$ | $\texttt{2s}$ | $n=m$ |
| #9~10 | $5\times 10^4$ | $3\times 10^4$ | $\texttt{2s}$ | |