A2569. 毒瘤之神的考验
编程题
NOI/NOI+/CTSC
知识点
题目描述
Salamander 的家门口是一条长长的公路。
又是一年春天将至，Salamander 发现路边长出了一排毒瘤！
Salamander 想带一些毒瘤回家，但是，这时毒瘤当中钻出来了一个毒瘤之神！
毒瘤之神：你想要带毒瘤走吗？想要带走毒瘤，就必须回答我的问题！如果答不出来的话，你还是乖乖回家吧！毒瘤之神会问 $T$ 次，每次给定 $n, m$，Salamander 需要回答出 $\left( \sum_{i=1}^n \sum_{j=1}^m \varphi(ij) \right)\! \bmod 998244353$。
Salamander 这么辣鸡当然不会做啦，于是把问题丢给了你。
又是一年春天将至，Salamander 发现路边长出了一排毒瘤！
Salamander 想带一些毒瘤回家，但是，这时毒瘤当中钻出来了一个毒瘤之神！
毒瘤之神：你想要带毒瘤走吗？想要带走毒瘤，就必须回答我的问题！如果答不出来的话，你还是乖乖回家吧！毒瘤之神会问 $T$ 次，每次给定 $n, m$，Salamander 需要回答出 $\left( \sum_{i=1}^n \sum_{j=1}^m \varphi(ij) \right)\! \bmod 998244353$。
Salamander 这么辣鸡当然不会做啦，于是把问题丢给了你。
输入格式
第一行包含一个正整数 $T$。
接下来 $T$ 行，每行包含两个正整数，用空格隔开，表示这次询问的 $n, m$。
接下来 $T$ 行，每行包含两个正整数，用空格隔开，表示这次询问的 $n, m$。
输出格式
包含 $T$ 行，每行一个整数表示答案。
输入输出样例
输入 #1
3 1 1 2 2 3 3
输出 #1
1 5 19
说明/提示
对于 $40\%$ 的数据，$T=1$，$n, m \le {10}^5$。
对于 $50\%$ 的数据，$T \le {10}^3$，$n, m \le {10}^5$。
对于另外 $10\%$ 的数据，$T \le {10}^4$，$n = m \le {10}^5$。
对于 $100\%$ 的数据，$1 \le T \le {10}^4$，$1 \le n, m \le {10}^5$。
对于 $50\%$ 的数据，$T \le {10}^3$，$n, m \le {10}^5$。
对于另外 $10\%$ 的数据，$T \le {10}^4$，$n = m \le {10}^5$。
对于 $100\%$ 的数据，$1 \le T \le {10}^4$，$1 \le n, m \le {10}^5$。