{"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## Input\n\n一行一个整数 $n$。\n\n## Output\n\n输出一个整数，表示喜爱程度和对 $10^9+7$ 取模的结果。\n\n[samples]\n\n## Background\n\nse 喜欢点阵。\n\n## Note\n\n### 样例解释 #1\n当 $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### 数据范围\n**本题采用捆绑测试**。\n|子任务编号|$n\\le$|分值|\n|:--:|:--:|:--:|\n|$1$|$8$|$5$|\n|$2$|$10^3$|$15$|\n|$3$|$10^6$|$30$|\n|$4$|$2^{31}-1$|$50$|\n\n对于 $100\\%$ 的数据，$1\\le n\\le 2^{31}-1$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10186","tags":["数论","素数判断,质数,筛法","莫比乌斯反演","杜教筛"],"sample_group":[["2","6"],["1919810","107114211"]],"created_at":"2026-03-03 11:09:25"}}