做网站抬头,wordpress标题字数,深圳做网站哪家专业,关于做网站的合同题意#xff1a;设f(i)f(i)f(i)表示iii的不严格次大质因子#xff08;没有为000#xff09;#xff0c;求∑ilrf(i)\sum_{il}^rf(i)∑ilrf(i) l≤r≤1011l\leq r\leq10^{11}l≤r≤1011
这种和质因数有关的奇奇怪怪的函数的前缀和可以试试魔改min_25筛
设 S(n,j)∑i2n[m…题意设f(i)f(i)f(i)表示iii的不严格次大质因子没有为000求∑ilrf(i)\sum_{il}^rf(i)∑ilrf(i)
l≤r≤1011l\leq r\leq10^{11}l≤r≤1011
这种和质因数有关的奇奇怪怪的函数的前缀和可以试试魔改min_25筛
设
S(n,j)∑i2n[minp(i)pj]f(i)S(n,j)\sum_{i2}^n[minp(i)p_j]f(i)S(n,j)i2∑n[minp(i)pj]f(i)
枚举最小的质因子pkp_kpk以及次数eee
如果pkp_kpk不是次大质因子直接递归到S(⌊npke⌋,k)S(\lfloor\frac{n}{p_k^e}\rfloor,k)S(⌊pken⌋,k)
否则考虑pkp_kpk的贡献
如果是严格次大那么枚举最大的质因子
否则就是[e1][e1][e1]
S(n,j)∑kj1pk≤n∑e1pke≤n(S(⌊npke⌋,k)∑ipk1⌊npke⌋[i∈prime][e1])S(n,j)\sum_{kj1}^{p_k\leq\sqrt n}\sum_{e1}^{p_k^e\leq n}(S(\lfloor\frac{n}{p_k^e}\rfloor,k)\sum_{ip_k1}^{\lfloor\frac{n}{p_k^e}\rfloor}[i\in prime][e1])S(n,j)kj1∑pk≤ne1∑pke≤n(S(⌊pken⌋,k)ipk1∑⌊pken⌋[i∈prime][e1])
注意pk1p_k1pk1可能大于⌊npke⌋\lfloor\frac{n}{p_k^e}\rfloor⌊pken⌋要特判一下
然后用min_25的方法预处理出质数个数的前缀和即可
#include iostream
#include cstdio
#include cstring
#include cctype
#include cmath
#define MAXN 1000005
using namespace std;
const int N1e6;
int np[MAXN],pl[MAXN],cnt;
void init()
{np[1]1;for (int i2;iN;i){if (!np[i]) pl[cnt]i;for (int j1,x;(xi*pl[j])N;j){np[x]1;if (i%pl[j]0) break;}}
}
typedef long long ll;
ll val[MAXN],n,m;
int key[MAXN],yek[MAXN],tot;
inline int getkey(ll x){return xm? key[x]:yek[n/x];}
ll g[MAXN];
ll S(ll n,int j)
{if ((ll)pl[j]*pl[j]n) return 0;ll sum0;for (int kj1;(ll)pl[k]*pl[k]nkcnt;k)for (ll e1,vpl[k];vn;e,v*pl[k])sumS(n/v,k)pl[k]*(max(0ll,g[getkey(n/v)]-k)(e1));return sum;
}
ll solve(ll N)
{msqrt(nN);tot0;for (ll l1,r;ln;lr1){rn/(n/l);val[tot]n/l;if (val[tot]m) key[val[tot]]tot;else yek[n/val[tot]]tot;}for (int i1;itot;i) g[i]val[i]-1;for (int j1;jcnt;j)for (int i1;(ll)pl[j]*pl[j]val[i];i)g[i]-g[getkey(val[i]/pl[j])]-j1;return S(n,0);
}
int main()
{init();ll l,r;cinlr;coutsolve(r)-solve(l-1);return 0;
}
