![]() |
||||||||||
|
||||||||||
图Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 11 Accepted Submission(s): 6 Problem Description 有一个$ n-1 $个点的无向图, 每个点的编号为$ 2..n $ 两个点$ u, v $ 之间存在一条边当且仅当 $ u $ 是 $ v $ 的倍数或者 $ v $ 是 $ u $ 的倍数 我们用$ c(u, v) $ 来描述两个点之间的联通状态, 用$\phi(x)$表示欧拉函数, 即$ 1..x-1 $中有多少个数与他互质 求 $$ \sum_{u = 2} ^ {n - 1} \sum_{v = u + 1} ^ {n} c(u, v) \phi(u) \phi(v) $$ Input 第一行一个$ T $ 描述数据组数 $ 1 \leq T \leq 10^6 $ 接下来$ T $行, 每行一个整数 $ n (1 \leq n \leq 10^7) $, 用来描述一组数据, 具体含义如上 Output $ T $ 行, 每行一个数用来描述上述式子对 $998244353$ 取模的结果 Sample Input
Sample Output
Hint 对于n = 5, 那么只有$2, 4$联通, 所以答案是2 Source | ||||||||||
|