[YDOI R1] Lattice

Luogu

IDLGP10186

Time1000ms

Memory512MB

DifficultyP6

数论素数判断,质数,筛法莫比乌斯反演杜教筛

se 有一个正方形点阵，这个点阵以 $(1,1)$ 为左下角，以 $(n,n)$ 为右上角。 se 还有一条直线，其表达式为 $y=kx$，其中 $k\in(0,\infty)$。对于任意一个 $k$，设该直线经过了 $cnt$ 个点阵中的点，se 对这条直线有一个喜爱程度，为 $cnt^2$。 se 想知道所有直线的喜爱程度和对 $10^9+7$ 取模的结果，请你告诉 se。 ## Input 一行一个整数 $n$。 ## Output 输出一个整数，表示喜爱程度和对 $10^9+7$ 取模的结果。 [samples] ## Background se 喜欢点阵。 ## Note ### 样例解释 #1 当 $k$ 为 $\frac{1}{2}$ 时，直线过点阵中的点 $(2,1)$，喜爱程度为 $1^2=1$；当 $k$ 为 $1$ 时，直线过点阵中的点 $(1,1)$ 和点 $(2,2)$，喜爱程度为 $2^2=4$；当 $k$ 为 $2$ 时，直线过点阵中的点 $(1,2)$，喜爱程度为 $1^2=1$。喜爱程度和为 $1+4+1=6$。 ### 数据范围 **本题采用捆绑测试**。 |子任务编号|$n\le$|分值| |:--:|:--:|:--:| |$1$|$8$|$5$| |$2$|$10^3$|$15$| |$3$|$10^6$|$30$| |$4$|$2^{31}-1$|$50$| 对于 $100\%$ 的数据，$1\le n\le 2^{31}-1$。

Samples

Input #1

Output #1

Input #2

Output #2

107114211

API Response (JSON)

{
  "problem": {
    "name": "[YDOI R1] Lattice",
    "description": {
      "content": "se 有一个正方形点阵，这个点阵以 $(1,1)$ 为左下角，以 $(n,n)$ 为右上角。 se 还有一条直线，其表达式为 $y=kx$，其中 $k\\in(0,\\infty)$。 对于任意一个 $k$，设该直线经过了 $cnt$ 个点阵中的点，se 对这条直线有一个喜爱程度，为 $cnt^2$。 se 想知道所有直线的喜爱程度和对 $10^9+7$ 取模的结果，请你告诉 se。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10186"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "se 有一个正方形点阵，这个点阵以 $(1,1)$ 为左下角，以 $(n,n)$ 为右上角。\n\nse 还有一条直线，其表达式为 $y=kx$，其中 $k\\in(0,\\infty)$。\n\n对于任意一个 $k$，设该直线经过了 $cnt$ 个点阵中的点，se 对这条直线有一个喜爱程度，为 $cnt^2$。\n\nse 想知道所有直线的喜爱程度和对 $10^9+7$ 取模的结果，请你告诉 se。\n\n## I...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments