{"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{n}{\\max(i,j)}\\rfloor [i \\perp j]\n$$\n\n其中 $[i \\perp j]$ 表示 $i,j$ 是否互素，即当 $\\gcd(i,j)=1$ 时，$[i \\perp j]$ 的值为 $1$，其余情况其值为 $0$。 \n\n## Input\n\n输入一行一个正整数 $n$ ($1\\le n \\le 10^9$)。\n\n## Output\n\n输出一行一个整数，表示这个和式的结果。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10532","tags":["数学","2024","O2优化","高校校赛"],"sample_group":[["2","4"]],"created_at":"2026-03-03 11:09:25"}}