创意来源https://blog.csdn.net/control bear/article/details/77527115 (约数个数/约数和线性筛)。
所谓欧拉筛，是将筛强制去除为线性o(n )的筛，
是线性筛的一种钦……
我对定义不太了解……
以下整理几个欧拉筛
筛素数prime、欧拉函数phi(n )、jzdhm函数(n ) ) ) ) )。
给出一定的证明过程
素数筛typedef long long ll； bool ok[maxn]； int prime[maxn]，cnt； void sieve () for ) llI=2； imaxn； I ) if (！ 确定ok[i] ) prime[cnt ]=i； for(intj=0； JNT； j ) if(I*prime[j]=maxn ) break； 确定ok[i*prime[j]]=1； if(I%prime[j]==0) break； }}每次用经过筛的素数筛出更大的数时，
各个因子被最小的质量因子筛选掉，
想想看。 如果2*6过筛12后还没有break，
相反，用3*6筛18，18用2*9再筛一次，重复
最根本的原因是6有2个因素，
3*6筛掉的数量也一定有2个因素，
3*6这个数应该被2而不是3这个因子筛选掉
2020年3月31日更新：
tls的欧拉筛，其中d[i]表示I的最小质因数
# include bits/stdc.husingnamespacestd； 泰普德夫龙龙LL； 常数上限=101； int t，tot，pr[maxp]，d[maxp]； int main () for ) intI=2； i maxp； I ) if (！ d[i] ) pr[tot ]=d[i]=i； for(intj=0，k； (k=i * pr[j] ) maxp； j () { d[k]=pr[j]； if(d ) I )==pr ) ) break； } }返回0； (欧拉函数筛) typedef long long ll； bool ok[maxn]； int prime[maxn]、phi[maxn]、cnt； void sieve () { phi[1]=1； for(LLI=2； imaxn； I ) if (！ k[I]}{prime[CNT]=I； phi[i]=i-1； }for(intj=0； JNT； j ) if(I*prime[j]=maxn ) break； 确定ok[i*prime[j]]=1； if(I%prime[j]==0) { phi [ I * prime [ j ] ]=phi [ I ] * prime [ j ]； //prime[j]表示I的因子prime[j]的质因数项包含在I的质因数项中的break； } else phi [ I * prime [ j ]=phi [ I ] * (prime [ j ]-1 )； //prime[j]和I相互交换phi [ I * prime [ j ]=phi [ I ] * phi [ prime [ j ] ]创意来源https://blog.csdn.net/bojack _
实际上，看prime[j]是否已经出现在I上，说明第一个出现减1，后面的不减
特判n==1，phi[1]=1
如果pi是质因数，
那么
对于i*prime[j]，
3358www.Sina.com/，prime[j]是素数，因此I包含prime[j]这个质因数，3358www.Sina.com/
所以呢
因为I里有同位素，
所以呢
3358www.Sina.com/和prime[j]是质数，因此I没有质因数prime[j]。i%prime[j]==0
从欧拉函数的乘积性可以看出，
然后，那个
所以呢
jzdhm函数筛(typedef long long ll； bool ok[maxn]； int prime[maxn]、mu[maxn]、cnt； void sieve () {mu[1]=1； for(LLI=2； imaxn； I ) if (！ k[I]}{prime[CNT]=I； mu[i]=-1； }for(intj=0； JNT； j ) if(I*prime[j]=maxn ) break； 确定ok[i*prime[j]]=1； if(I%prime[j]==0) {mu[i*prime[j]]=0； //如果你在全球运行，你可以不介意break； }else mu[i*prime[j]]=-mu[i]； } }
图为百度百科： jzd
hm函数特判n==1，mu[1]=1
对于一个素数p，μ(p)=-1
而一个数i*prime[j]被最小素因子prime[j]筛到的时候，
①i%prime[j]!=0,i里没有prime[j]这个素因子
i*prime[j]是比i多一个素因子prime[j]的，
所以μ(i*prime[j])=-μ(i)即可
②i%prime[j]==0，i里有prime[j]这个素因子
说明i*prime[j]里至少有两个prime[j]这个素因子，
根据jzdhm函数定义，μ(i*prime[j])=0，
开全局变量的话就不用管
搞个三合一板好了，以后直接粘着用……
#include<iostream>#include<cstdio>#include<cstring>using namespace std;typedef long long ll;const int maxn=1e6+10;bool ok[maxn];int prime[maxn],phi[maxn],mu[maxn],cnt;void sieve(){phi[1]=mu[1]=1;for(ll i=2;i<maxn;++i){if(!ok[i]){prime[cnt++]=i;phi[i]=i-1;mu[i]=-1;}for(int j=0;j<cnt;++j){ll k=i*prime[j];if(k>=maxn)break;ok[k]=1;if(i%prime[j]==0){phi[k]=phi[i]*prime[j];mu[k]=0;break; }else{ phi[k]=phi[i]*(prime[j]-1); mu[k]=-mu[i]; }}}}int main(){sieve(); return 0;} ④积性函数线性筛思路来源：https://www.cnblogs.com/zwfymqz/p/9337898.html
线性筛中，k只会被最小素因子prime[j]筛到，
所以，分i是否有prime[j]这个素因子，是否全为prime[j]这个素因子来讨论
约数个数线性筛、约数和线性筛都是这个思想，可参考上述链接
以2019南京网络赛 E.K Sum为例，这里，sieve中的f[]是一个积性函数
#include<iostream>#include<cstdio>#include<cstring>#include<map>using namespace std;typedef long long ll;const int mod=1e9+7;const int maxn=1e7+10;const int inv6=(mod+1)/6;const int N=1e5+10;bool ok[maxn];int prime[maxn],cnt;int low[maxn],lowp[maxn];ll f[maxn];int T,n,len,x;ll res,v;char s[N];map<int,ll>ff;void sieve(){ f[1]=1; for(ll i=2;i<maxn;++i) { if(!ok[i]) { prime[cnt++]=i; low[i] = lowp[i] = i; f[i] =(i*i-1)%mod;/*i为质数的情况f(p)*/ } for(int j=0;j<cnt;++j) { ll k=i*prime[j]; if(k>=maxn)break; ok[k]=1; if(i%prime[j]==0)//i中出现过prime[j] { low[k]=prime[j]; lowp[k]=lowp[i]*prime[j]; if(i==lowp[i])f[k]=f[i]*(f[prime[j]]+1)%mod;/*i中全为prime[j] f(p^k)的情况*/ else f[k]=f[i/lowp[i]]*f[lowp[i]*prime[j]]%mod;/*i中不全为prime[j] 将最小素因子prime[j]和其他分开 显然互质*/ break; } else { low[k]=lowp[k]=prime[j]; f[k]=f[i]*f[prime[j]]%mod;//i中没出现过prime[j] i与prime[j]互质 } } } for(int i=2;i<maxn;++i) { f[i]=(f[i]+f[i-1])%mod; }}ll modpow(ll x,ll n,ll mod){ll res=1;for(;n;n/=2,x=x*x%mod)if(n&1)res=res*x%mod;return res;}ll cal(ll x){ll inv=modpow(x-1,mod-2,mod);ll y=modpow(x,v,mod);ll z=modpow(x,2,mod);return (y-z+mod)%mod*inv%mod;}ll getf(int n){if(n<maxn)return f[n];if(ff.count(n))return ff[n];ll ans=1ll*n*(n+1)%mod*(2*n+1)%mod*inv6%mod;for(int l=2,r;l<=n;l=r+1){r=n/(n/l);ans=(ans+mod-1ll*(r-l+1)*getf(n/l)%mod)%mod;} return ff[n]=ans;}ll solve(int n){ll ans=0; for(int l=1,r;l<=n;l=r+1) { r=n/(n/l); if(r==n)ans=(ans+(getf(r)-getf(l-1)+mod)%mod*(res-1+mod)%mod)%mod; else ans=(ans+(getf(r)-getf(l-1)+mod)%mod*cal(n/l)%mod)%mod; } return ans;}int main(){ sieve(); scanf("%d",&T); while(T--) { scanf("%d%s",&n,s); len=strlen(s); res=0;v=0; for(int i=0;i<len;++i) {res=(res*10+(s[i]-'0'))%mod;v=(v*10+(s[i]-'0'))%(mod-1);}v=(v+1)%(mod-1); printf("%lldn",solve(n)); } return 0;}