[JRKSJ R6] 牵连的世界

Luogu

IDLGP8570

Time1700ms

Memory256MB

DifficultyP7

2022洛谷原创O2优化素数判断,质数,筛法莫比乌斯反演

给定 $n,m$，求 $$\sum_{i=1}^n \sum_{j=1}^m \sigma_0(ij)\varphi(ij)$$ ## Input 两个整数 $n,m$。 ## Output 一个整数，表示答案。答案对 $10^9+7$ 取模。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/jdi9nrec.png) ## Note $\sigma_0,\varphi$ 分别为因数个数函数，欧拉函数。本题可能轻微卡常。 ### 数据规模本题采用捆绑测试。 | $\text{Subtask}$ | $n,m\le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $10^3$ | $10$ | | $2$ | $10^5$ | $30$ | | $3$ | $2\times 10^5$ | $30$ | | $4$ | $5\times 10^5$ | $30$ | | $5$ | $3\times 10^6$ | $1$ | 对于所有数据，$1\le n,m\le 3\times 10^6$。出于某些原因，你只要得到了 $\ge 100$ 分就可以通过此题。

Samples

Input #1

5 5

Output #1

Input #2

20 20

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[JRKSJ R6] 牵连的世界",
    "description": {
      "content": "给定 $n,m$，求 $$\\sum_{i=1}^n \\sum_{j=1}^m \\sigma_0(ij)\\varphi(ij)$$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1700,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8570"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n,m$，求\n\n$$\\sum_{i=1}^n \\sum_{j=1}^m \\sigma_0(ij)\\varphi(ij)$$\n\n## Input\n\n两个整数 $n,m$。\n\n## Output\n\n一个整数，表示答案。答案对 $10^9+7$ 取模。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hos...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments