一径入繁华

Luogu
IDLGP10182
Time2000ms
Memory512MB
DifficultyP7
数学数论洛谷原创O2优化线性代数洛谷月赛
帆巨觉得求 $x^a$ 在 $\bmod\ p$ 意义下的值太简单了,所以他想求 $\sigma_0^s(x^t)$ 在 $\bmod\ p$ 意义下的值。 帆帆不满足于只计算一次,于是他列了一个 $n\times n$ 的数表 $A$,保证第 $i$ 行第 $j$ 列($1\le i,j\le n$)中的元素 $a_{i,j}$ 满足: $$ a_{i,j}=\sum_{d\mid \gcd(i,j)}\mu\left(\dfrac{\gcd(i,j)}{d}\right)\times (\sigma_0(d^s))^t $$ 帆帆想知道这个数表长什么样子,但这个数表实在太大了,所以请你告诉他 $\det A$ 对 $10^9+7$ 取模后的结果。 注释: 1. 表达式中的各种函数含义在 **[这里](https://oi-wiki.org/math/number-theory/basic/#%E4%BE%8B%E5%AD%90)($\mu$ 表示莫比乌斯函数,$\sigma_0$ 表示约数个数函数)**。 2. $\det A$ 表示方阵 $A$ 的 **[行列式](https://baike.baidu.com/item/%E8%A1%8C%E5%88%97%E5%BC%8F/2010180)**。 ## Input 一行,输入三个整数 $n,s,t$。 ## Output 一行,输出一个整数表示答案。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/68qtrpb7.png) 伴随龙年到来的,还有帆巨很喜欢的九省联考。为了爆踩压轴题。帆巨狠狠地重温了数论。 数论所生,繁华之地! ## Note ### 【样例 $1$ 解释】 矩阵 $A$ 如下: $$ \begin{bmatrix} 1 & 1\\ 1 &3 \end{bmatrix} $$ 行列式为 $1\times 3 - 1\times 1=2$。 ### 【样例 $2$ 解释】 矩阵 $A$ 如下: $$ \begin{bmatrix} 1 & 1\\ 1 & 255 \end{bmatrix} $$ 行列式为 $1\times 255 - 1 \times 1=254$。 ### 数据范围 本题采用 **子任务捆绑测试**。 对于 $100\%$ 的数据,保证 $1\le n\le 10^{11}$,$0\le s,t< 10^9+7$。 | 子任务编号 | $n$ | 特殊性质 | 分值 | | :---------: | :-----------: | :-------: | :--: | | Subtask #1 | $\le 500$ | 无 | $8$ | | Subtask #2 | $\le 10^7$ | $s=1,t=2$ | $5$ | | Subtask #3 | $\le 10^7$ | $s=1$ | $10$ | | Subtask #4 | $\le 10^{11}$ | $s=1,t=2$ | $10$ | | Subtask #5 | $\le 10^{11}$ | $s=1$ | $10$ | | Subtask #6 | $\le 10^{11}$ | $t=1$ | $2$ | | Subtask #7 | $\le 10^{7}$ | $t\le 9$ | $10$ | | Subtask #8 | $\le 10^{11}$ | $t\le 9$ | $15$ | | Subtask #9 | $\le 10^7$ | 无 | $10$ | | Subtask #10 | $\le 10^{11}$ | 无 | $20$ | **特殊性质** 一栏为空则表示没有特殊性质。子任务中没有规定范围的变量的值均在 $[0,10^9+7)$ 范围内生成。 时间限制:$\text{2000 ms}$; 空间限制:$\text{512 MB}$。
Samples
Input #1
2 1 2
Output #1
2
Input #2
2 3 4
Output #2
254
Input #3
19 8 10
Output #3
913255725
Input #4
10000000000 1 2
Output #4
880793261
API Response (JSON)
{
  "problem": {
    "name": "一径入繁华",
    "description": {
      "content": "帆巨觉得求 $x^a$ 在 $\\bmod\\ p$ 意义下的值太简单了,所以他想求 $\\sigma_0^s(x^t)$ 在 $\\bmod\\ p$ 意义下的值。 帆帆不满足于只计算一次,于是他列了一个 $n\\times n$ 的数表 $A$,保证第 $i$ 行第 $j$ 列($1\\le i,j\\le n$)中的元素 $a_{i,j}$ 满足: $$ a_{i,j}=\\sum_{d\\mid \\gcd",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10182"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "帆巨觉得求 $x^a$ 在 $\\bmod\\ p$ 意义下的值太简单了,所以他想求 $\\sigma_0^s(x^t)$ 在 $\\bmod\\ p$ 意义下的值。\n\n帆帆不满足于只计算一次,于是他列了一个 $n\\times n$ 的数表 $A$,保证第 $i$ 行第 $j$ 列($1\\le i,j\\le n$)中的元素 $a_{i,j}$ 满足:\n\n$$\na_{i,j}=\\sum_{d\\mid \\gcd...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments