【洛谷】P3601 签到题

洛谷P3601 签到题

题目描述 我们定义一个函数：qiandao(x)为小于等于x的数中与x不互质的数的个数。

这题作为签到题，给出l和r，要求求${\sum }_{i=l}^{r}qiandao(i)mod666623333$.

输入格式 一行两个整数，l、r。

输出格式 一行一个整数表示答案。

输入输出样例 输入 #1

233 2333

输出 #1

1056499

说明/提示

对于100%的数据，$1\le l\le r\le 10^{12},r-l\le 10^6$.

这题一看就是要求l到r范围内所有x，与x不互质且小于等于x的数个数。一看数据范围，l和r是$10^{12}$范围，暴力不太行，但r-l的范围却是可观的。考虑用数组phi[i]存储与l+i互质且小于等于i的元素个数。最关键的是欧拉函数的公式别忘记了： $$\phi (x)=x\prod _{i=1}^n(1-\frac{1}{p_i})$$ 其中$p_1,p_2,\cdots ,p_n$为x所有质因数。那么接下来就需要求l到r范围内数的所有质因数，一个个遍历不太好，比较好的办法是先预处理出来$10^6$范围内的素数（基础的线性筛），然后遍历这些素数，将i的phi初始化为i，如果i含有这个素因子就减小。代码如下：

now标记素数 数组primes当前的位置，isprime用于预处理素数。phi[i]表示i+l的欧拉函数，remain[i]表示i+l除掉之前的素因子之后还剩下什么。由于处理$10^6$以上的素因子开销太大，而这么大的素因子的个数至多一个，所以如果最后remain[i]>1，就说明这是一个大于$10^6$的素因子。 #include<bits/stdc++.h> using namespace std; long l,r,now=1,res=0,mod=666623333; long isprime[1000010],primes[1000010]; long phi[1000010],remain[1000010]; void build(){ isprime[1]=0; for(int i=2;i<=1e6;i++){ if(isprime[i]){ primes[now++]=i; } for(int j=1;j<now&&primes[j]*i<=1e6;j++){ isprime[primes[j]*i]=0; if(i%primes[j]==0) break; } } } int main(){ cin>>l>>r; memset(isprime,1,sizeof(isprime)); build(); for(long i=l;i<=r;i++){ phi[i-l]=i; remain[i-l]=i; } for(long i=1;i<now&&primes[i]*primes[i]<=r;i++){ long p=primes[i]; for(long j=((l-1)/p+1)*p;j<=r;j+=p){ phi[j-l]=phi[j-l]/p*(p-1); while(remain[j-l]%p==0) remain[j-l]/=p; } } for(long i=l;i<=r;i++){ if(remain[i-l]>1){ phi[i-l]=phi[i-l]/remain[i-l]*(remain[i-l]-1); } res=(res+i-phi[i-l])%mod; } cout<<res; return 0; }