Two Hypercubes

Luogu

IDLGP8380

Time2500ms

Memory512MB

DifficultyP6

数学洛谷原创O2优化洛谷月赛

$T$ 次询问，每次给定 $A,B,C$，求： $$\Big(\sum_{x=1}^A\sum_{y=1}^B\sum_{z=1}^C[y^x=x^z]\Big)\bmod (10^9+7).$$ ## Input 第一行一个正整数 $T$。接下来 $T$ 行，每行三个正整数 $A,B,C$。 ## Output $T$ 个整数 $\text{ans}$ 表示答案。以换行符隔开。 [samples] ## Background 注：数据已经加强。 ## Note 【样例 1 解释】第一组询问 $A=1,B=2,C=3$，满足条件的三元组 $(x,y,z)$ 有 $(1,1,1),(1,1,2),(1,1,3).$ 第二组询问 $A=3,B=4,C=5$，满足条件的三元组 $(x,y,z)$ 有： $(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,1,5),(2,2,2),(2,4,4),(3,3,3).$ 第三组询问 $A=6,B=7,C=8$，满足条件的三元组 $(x,y,z)$ 有： $(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,1,5),(1,1,6),(1,1,7),(1,1,8);$ $(2,2,2),(2,4,4),(3,3,3),(4,2,2),(4,4,4),(5,5,5),(6,6,6).$ --- 【数据范围】对 $100\%$ 的数据，满足 $1\leq T\leq 2\times 10^4,\ 1\leq A,B,C\leq 10^{18}$。 - $\text{Subtask}\ 0(5\ \text{pts})$：$T,A,B,C\leq 11$。 - $\text{Subtask}\ 1(7\ \text{pts})$： $T\leq 20,\ A,B,C\leq 3333$。 - $\text{Subtask}\ 2(17\ \text{pts})$：$T\leq 20,\ A,B\leq 10^{10},\ C\leq 3333$。 - $\text{Subtask}\ 3(17\ \text{pts})$：$T\leq 20,\ A,B,C\leq 10^{10}$。 - $\text{Subtask}\ 4(27\ \text{pts})$：$A,B,C\leq 10^{11}$。 - $\text{Subtask}\ 5(27\ \text{pts})$：无特殊限制。

Samples

Input #1

Output #1

3
8
15

Input #2

2
999 9999 99999
2000 20000 200000

Output #2

101202
202276

API Response (JSON)

{
  "problem": {
    "name": "Two Hypercubes",
    "description": {
      "content": "$T$ 次询问，每次给定 $A,B,C$，求： $$\\Big(\\sum_{x=1}^A\\sum_{y=1}^B\\sum_{z=1}^C[y^x=x^z]\\Big)\\bmod (10^9+7).$$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8380"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$T$ 次询问，每次给定 $A,B,C$，求：\n\n$$\\Big(\\sum_{x=1}^A\\sum_{y=1}^B\\sum_{z=1}^C[y^x=x^z]\\Big)\\bmod (10^9+7).$$\n\n## Input\n\n第一行一个正整数 $T$。\n\n接下来 $T$ 行，每行三个正整数 $A,B,C$。\n\n## Output\n\n$T$ 个整数 $\\text{ans}$ 表示答案。以换行符隔开。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments