常用莫比乌斯套路
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/a1c6d25c59b2c459a4bcb6c262f40076" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/852aad7f9bdde9fc06c5b4d532946836" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/a62af6d5e32e6269c9e27cad43572f75" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/a61e421efdef59c5eb2a013c9a24660d" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/10a7e4eb4e86c7b9312d719789eb092d" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/414ed4f6d54df2ede2501c8c02eb6730" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/9df474df4d6604a4a6f7c2dc6f10e021" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/15a1efbbc2c254cd7bc7b8e551ffb346" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/81344c6b8a3895574b051175b3229d30" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/f92e027c51697f3710e39e2497dd3fe1" alt="" /></p>
<pre><code class="language-cpp">void sieve() {
F[1]=sum[1]=1;
for (int i=2;i<=10000000;i++) {
if (!flag[i]) prime[++cnt]=i,F[i]=1-i;
for (int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
flag[i*prime[j]]=1;
if (i%prime[j]==0) {//不互质
F[i*prime[j]]=F[i];
break;
}
F[i*prime[j]]=F[i]*F[prime[j]];//互质
}
sum[i]=sum[i-1]+F[i]*i;
}
}</code></pre>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/5d8549fd007a41004bb218f72de09f76" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/b1a318457544cc2a00e90fe537abbbd9" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/1f212830919dad14fa317b4d49ac8c42" alt="" />
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/9240003502c21ce952e2e2f99c6406f6" alt="" /></p>