Description：

$f(n)=n的次大质因子$ ，计算次大质因子时多个按多个算，特别的 $f(p)=f(1)=0$ ，求： $$ \sum_{i=1}^nf(i) $$ $1\leqslant n\leqslant 10^{11}$

Solution：

$f$ 并不积性，但是并不妨碍我们用 $\min\_25$ 筛，我们把每个数在他只剩两个质因子的时候计算，因为如果只剩一个质因子也就是质数答案是 $0$ ，也就是说如果在递归到当前时他被消成了一个质数，那么我们就统计这个数的贡献，他的次大质因子就应该是 $prime[j-1]$ ，这些数的个数显然就是比 $prime[j-1]$ 大的质数的个数，也就是 $g(n,|p|)-(j-1)$ ，这部分的贡献就是， $prime[j-1]\times(g(n,|p|)-(j-1))$ 再考虑其他的贡献，还是设 $S(n,j)$ 表示 $1\sim n$ 中最小质因子 $\geqslant j$ 的数的和 $$ S(n,j)=\sum_{k=j}^{p_k^2\leqslant n}\sum_{e=1}^{p_k^{e+1}\leqslant n}(S(\frac n{p^e_k},k+1)+prime[j]) $$ 也就是说如果我们不需要进行把 $f$ 提出来这样的操作 $f$ 是否积性其实是不重要的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll l,r;

#define MAXN 1000010

int N;

bool isprime[MAXN];

int prime[MAXN],tot = 0;

void sieve()

{

	tot = 0;

	for(int i = 2;i <= N;++i)isprime[i] = true;

	for(int i = 2;i <= N;++i)

	{

		if(isprime[i])prime[++tot] = i;

		for(int j = 1;j <= tot && i * prime[j] <= N;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)break;

		}

	}

	return;

}

int id1[MAXN],id2[MAXN];

ll nn;

int id(ll k){return (k <= N ? id1[k] : id2[nn / k]);}

int g[MAXN];

ll w[MAXN];

int m = 0;

ll S(ll n,int j)

{

	if(n <= 1 || prime[j] > n)return 0;

	int k = id(n);

	ll res = 1ll * prime[j - 1] * (g[k] - (j - 1));

	for(int k = j;k <= tot && 1ll * prime[k] * prime[k] <= n;++k)

	{

		ll p1 = prime[k],p2 = 1ll * prime[k] * prime[k];

		for(int e = 1;p2 <= n;++e,p1 = p2,p2 *= prime[k])

		{

			res += S(n / p1,k + 1) + prime[k];

		}

	}

	return res;

}

ll calc(ll n)

{

	if(n == 0)return 0;

	nn = n;

	N = sqrt(n);

	sieve();

	m = 0;

	for(ll l = 1,r;l <= n;l = r + 1)

	{

		r = n / (n / l);

		w[++m] = n / l;

		if(w[m] <= N)id1[w[m]] = m;

		else id2[n / w[m]] = m;

		g[m] = w[m] - 1;

	}

	for(int j = 1;j <= tot;++j)

	{

		for(int i = 1;i <= m && 1ll * prime[j] * prime[j] <= w[i];++i)

		{

			int k = id(w[i] / prime[j]);

			g[i] = g[i] - g[k] + j - 1;

		}

	}

	return S(n,1);

}

int main()

{

	scanf("%lld%lld",&l,&r);

	cout << calc(r) - calc(l - 1) << endl;

	return 0;

}