企业电子商务网站建设设计目的,个人网站我的大学我做主页面,鹤壁建设网站推广渠道,公众号制作技巧题面 传送门 题解 这是一道语文题 不难看出#xff0c;题目所求即为\(l\)到\(r\)中每个数的次大质因子 我们考虑\(Min\_25\)筛的过程#xff0c;设 \[S(n,j)\sum_{i1}^nsec_p(i)[min_p(i)\geq P_j]\] 用人话来说的话#xff0c;就是\(S(n,j)\)表示\(1\)到\(n\)之间所有满足最…题面 传送门 题解 这是一道语文题 不难看出题目所求即为\(l\)到\(r\)中每个数的次大质因子 我们考虑\(Min\_25\)筛的过程设 \[S(n,j)\sum_{i1}^nsec_p(i)[min_p(i)\geq P_j]\] 用人话来说的话就是\(S(n,j)\)表示\(1\)到\(n\)之间所有满足最小值因子大于等于\(P_j\)的\(i\)的次大质因子之和 我们照例把质数和合数的贡献分开考虑。所有质数贡献为\(0\)而对于合数我们枚举最小质因子\(P_k\)。此时分为两种情况如果\(P_k\)不是次大质因子那么\(S(n,j)\)要加上所有满足\(kj\)的\(S(\left\lfloor\frac{n}{{P_k}^e}\right\rfloor,k1)\)。如果\(P_k\)是次大质因子那么剩下的数肯定是一个大于等于\(P_k\)的质因子也就是\(P_k\)到\(\left\lfloor\frac{n}{{P_k}^e}\right\rfloor\)之间质数的个数 用从隔壁大佬那里偷来的公式来写的话就是这样子 \[S(n,j)\sum_{k\ge j}\sum_{e1}^{p_k^{e1}\le n}S(\lfloor\frac{n}{p^{e}_k}\rfloor,k1)p_k\sum_{ip_k}^{\lfloor\frac{n}{p^{e}_k}\rfloor}[i\in P]\] //minamoto
#includebits/stdc.h
#define R register
#define ll long long
#define fp(i,a,b) for(R int ia,Ib1;iI;i)
#define fd(i,a,b) for(R int ia,Ib-1;iI;--i)
#define go(u) for(int ihead[u],ve[i].v;i;ie[i].nx,ve[i].v)
using namespace std;
const int N1e65;
int p[N],id1[N],id2[N],m,tot,sqr;bitsetNvis;
ll l,r,qwq,w[N],g[N];
void init(int n){fp(i,2,n){if(!vis[i])p[tot]i;for(R int j1;jtot1ll*i*p[j]n;j){vis[i*p[j]]1;if(i%p[j]0)break;}}
}
ll S(ll n,int m){if(n2||p[m]n)return 0;ll res0;for(R int im;itot1ll*p[i]*p[i]n;i)for(R ll tmpp[i];tmp*p[i]n;tmp*p[i]){int k(n/tmpsqr)?id1[n/tmp]:id2[qwq/(n/tmp)];resS(n/tmp,i1)(g[k]-i1)*p[i];}return res;
}
ll calc(ll n){qwqn,m0;for(R ll i1,j;in;ij1){jn/(n/i),w[m]n/i;w[m]sqr?id1[w[m]]m:id2[n/w[m]]m;g[m]w[m]-1;}fp(j,1,tot)for(R int i1;1ll*p[j]*p[j]w[i];i){int k(w[i]/p[j]sqr)?id1[w[i]/p[j]]:id2[n/(w[i]/p[j])];g[i]g[i]-g[k]j-1;}return S(n,1);
}
int main(){
// freopen(testdata.in,r,stdin);scanf(%lld%lld,l,r),init(sqrsqrt(r));printf(%lld\n,calc(r)-calc(l-1));return 0;
} 转载于:https://www.cnblogs.com/bztMinamoto/p/10415464.html
