[GESP202403 八级] 公倍数问题

Luogu

IDLGP10263

Time1000ms

Memory128MB

DifficultyP3

数学2024GESP调和级数

小 A 写了一个 $N \times M$ 的矩阵 $A$，我们看不到这个矩阵，但我们可以知道，其中第 $i$ 行第 $j$ 列的元素 $A_{i,j}$ 是 $i$ 和 $j$ 的公倍数（$i=1,\dots,N$，$j=1,\dots,M$）。现在有 $K$ 个小朋友，其中第 $k$ 个小朋友想知道，矩阵 $A$ 中最多有多少个元素可以是 $k$（$k=1,2,\dots,K$）。请你帮助这些小朋友求解。注意：每位小朋友的答案互不相关，例如，有些位置既可能是 $x$，又可能是 $y$，则它同时可以满足 $x,y$ 两名小朋友的要求。方便起见，你只需要输出 $\sum_{k=1}^{K}{k \times \texttt{ans}_k}$ 即可，其中 $\texttt{ans}_k$ 表示第 $k$ 名小朋友感兴趣的答案。 ## Input 第一行三个正整数 $N,M,K$。 ## Output 输出一行，即 $\sum_{k=1}^{K}{k \times \texttt{ans}_k}$。请注意，这个数可能很大，使用 C++ 语言的选手请酌情使用 `long long` 等数据类型存储答案。 [samples] ## Background 对应的选择、判断题：<https://ti.luogu.com.cn/problemset/1148> ## Note ### 样例 1 解释只有 $A_{1,1}$ 可以是 $1$，其余都不行。 $A_{1,1},A_{1,2},A_{2,1},A_{2,2}$ 都可以是 $2$，而其余不行。因此答案是 $1 \times 1 + 2 \times 4 = 9$。 ### 数据规模对于 $30\%$ 的测试点，保证 $N,M,K \leq 10$；对于 $60\%$ 的测试点，保证 $N,M,K \leq 500$；对于 $100\%$ 的测试点，保证 $N,M \leq 10^5$，$K \leq 10^6$。

Samples

Input #1

2 5 2

Output #1

Input #2

100 100 100

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[GESP202403 八级] 公倍数问题",
    "description": {
      "content": "小 A 写了一个 $N \\times M$ 的矩阵 $A$，我们看不到这个矩阵，但我们可以知道，其中第 $i$ 行第 $j$ 列的元素 $A_{i,j}$ 是 $i$ 和 $j$ 的公倍数（$i=1,\\dots,N$，$j=1,\\dots,M$）。现在有 $K$ 个小朋友，其中第 $k$ 个小朋友想知道，矩阵 $A$ 中最多有多少个元素可以是 $k$（$k=1,2,\\dots,K$）。请你帮助这些",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10263"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 A 写了一个 $N \\times M$ 的矩阵 $A$，我们看不到这个矩阵，但我们可以知道，其中第 $i$ 行第 $j$ 列的元素 $A_{i,j}$ 是 $i$ 和 $j$ 的公倍数（$i=1,\\dots,N$，$j=1,\\dots,M$）。现在有 $K$ 个小朋友，其中第 $k$ 个小朋友想知道，矩阵 $A$ 中最多有多少个元素可以是 $k$（$k=1,2,\\dots,K$）。请你帮助这些...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments