题解：SP22268 ETFS - Euler Totient Function Sieve

· · 题解

前置知识

欧拉函数以及求法。

思路

我们知道欧拉函数值有递推的求法还有单个值的求法。对于此题，b<10^{14} 肯定不能递推去求，b-a\le10^5 也明显提醒我们是去一个一个求。对于求单个欧拉函数的值，我们是需要质因数分解的，但是把 10^{14} 内所有的质数给求出来复杂度是不行的。此时我们考虑，对于一个数 n，他大于 \sqrt{n} 的质因子最多只有一个。所以我们只需要将他小于等于 \sqrt{n} 的质因子全部除掉之后，剩下的就是那个大于 \sqrt{n} 的质因子。证明很简单，如果有超过两个大于 \sqrt{n} 的质因子，那么这个数肯定是大于 n 的。这也就是说，我们只需要求出 \sqrt{b} 内所有的质数，就可以将小于 b 的所有数质因数分解。

处理完质数的问题之后，我们考虑如何给 a\sim b 之间的每个数质因数分解。直接暴力肯定是不行的。我们反过来想，去对于每个质因子，考虑区间内哪些数是他的倍数。此时，我们就不用一个数一个数的去枚举了，只需找找到区间内最小的是这个质因子倍数的数，然后每次将这个数加上这个质因子即可找到区间内全部的它的倍数。

最后，我们已经分解完区间内所有数的质因数了，只需要将求欧拉函数值的公式带进去求一下就行了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int p[670000],a,b,tot,w[100005],x[100005];
bool bj[100000001];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>a>>b;
    for(int i=2;i<=sqrt(b);i++){
        if(!bj[i]){
            p[++tot]=i;
        }
        for(int j=1;j<=tot&&i*p[j]<=sqrt(b);j++){
            bj[i*p[j]]=1;
            if(i%p[j]==0)
                break;
        }
    }//线性筛素数
    for(int i=a;i<=b;i++){
        x[i-a+1]=w[i-a+1]=i;
    }
    for(int i=1;i<=tot;i++){
        int tmp=ceil(1.00*a/p[i])*p[i];//找到区间内最小的为这个质数倍数的数
        while(tmp<=b){//在不超出区间的情况下一直往后跳
            w[tmp-a+1]/=p[i];//求答案
            w[tmp-a+1]*=(p[i]-1);
            while(x[tmp-a+1]%p[i]==0){//把这个质因子全部除掉
                x[tmp-a+1]/=p[i];
            }
            tmp+=p[i];
        }
    }
    for(int i=a;i<=b;i++){
        if(x[i-a+1]>1){//注意还可能有大于 $\sqrt{n}$ 的质因子
            w[i-a+1]/=x[i-a+1];
            w[i-a+1]*=(x[i-a+1]-1);
        }
    }
    for(int i=a;i<=b;i++){
        cout<<w[i-a+1]<<'\n';
    }
    return 0;
}

AC 记录。