#埃氏筛，欧拉函数#洛谷 3601 签到题

本文主要是介绍#埃氏筛，欧拉函数#洛谷 3601 签到题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

求$$\sum _{i=l}^{r}i-\phi (i)$$

---

分析

首先这道题数据范围非常大，杜教筛是不可能的，所以只能用$r-l\le 10^6$这一条件，那么首先预处理$10^6$以内的质数，然后用这些质数求欧拉函数，对于大质数，当然是用另外一个数组记录下来然后特判，时间复杂度$O(10^{6}log10^6)$

---

代码

#include <cstdio>
#define rr register
using namespace std;
const int N=1000000;
typedef long long ll; int prime[80001],cnt;
ll l,r,phi[N+1],b[N+1],ans; bool v[N+1];
signed main(){for (rr int i=2;i<=N;++i)if (!v[i]){prime[++cnt]=i;for (rr int j=i<<1;j<=N;j+=i)v[j]=1;}scanf("%lld%lld",&l,&r);for (rr int i=1;i<=r-l+1;++i) phi[i]=b[i]=i+l-1;for (rr int i=1;i<=cnt&&prime[i]*prime[i]<=r;++i){rr ll L=prime[i]*(l/prime[i]),R=prime[i]*(r/prime[i]);for (rr ll j=L;j<=R;j+=prime[i])if (j>=l){phi[j-l+1]=phi[j-l+1]/prime[i]*(prime[i]-1);while (b[j-l+1]%prime[i]==0) b[j-l+1]/=prime[i];}}for (rr int i=1;i<=r-l+1;++i){if (b[i]>1) phi[i]=phi[i]/b[i]*(b[i]-1);ans=(ans+l+i-1-phi[i])%666623333;}return !printf("%lld",ans);
}

这篇关于#埃氏筛，欧拉函数#洛谷 3601 签到题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---