[XJTUPC 2024] 筛法

Luogu

IDLGP10532

Time1000ms

Memory256MB

DifficultyP4

数学2024O2优化高校校赛

在算法竞赛的数论知识中，我们接触过埃拉托斯特尼筛法、线性筛法、莫比乌斯反演、杜教筛、Powerful Number 筛、Min\_25 筛、洲阁筛等算法来帮助我们优化一些求和/连乘的复杂度，那么现在问题来了，今天这道题将会使用到上述的哪个算法呢？现在给定正整数 $n$，需要你求 $$ \sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor \dfrac{n}{\max(i,j)}\rfloor [i \perp j] $$ 其中 $[i \perp j]$ 表示 $i,j$ 是否互素，即当 $\gcd(i,j)=1$ 时，$[i \perp j]$ 的值为 $1$，其余情况其值为 $0$。 ## Input 输入一行一个正整数 $n$ ($1\le n \le 10^9$)。 ## Output 输出一行一个整数，表示这个和式的结果。 [samples]

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[XJTUPC 2024] 筛法",
    "description": {
      "content": "在算法竞赛的数论知识中，我们接触过埃拉托斯特尼筛法、线性筛法、莫比乌斯反演、杜教筛、Powerful Number 筛、Min\\_25 筛、洲阁筛等算法来帮助我们优化一些求和/连乘的复杂度，那么现在问题来了，今天这道题将会使用到上述的哪个算法呢？ 现在给定正整数 $n$，需要你求  $$ \\sum\\limits_{i=1}^n\\sum\\limits_{j=1}^n\\lfloor \\dfrac{",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10532"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在算法竞赛的数论知识中，我们接触过埃拉托斯特尼筛法、线性筛法、莫比乌斯反演、杜教筛、Powerful Number 筛、Min\\_25 筛、洲阁筛等算法来帮助我们优化一些求和/连乘的复杂度，那么现在问题来了，今天这道题将会使用到上述的哪个算法呢？\n\n现在给定正整数 $n$，需要你求 \n\n$$\n\\sum\\limits_{i=1}^n\\sum\\limits_{j=1}^n\\lfloor \\dfrac{...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments