链接
uoj
题意
求 $[l,r]$ 内整数的次大质因子（重复算多次）的和。质数的次大质因子为 $0$。
$l+r,r\leq 10^{11}$
题解
看着数据范围显然要往Min25的方向去想。
但是这个东西并不是积性函数。我们考虑Min25的第二部分，即求 $S(n,j)$ 的地方。
普通的Min25筛做法是分别考虑质数与合数的贡献，这里质数的贡献是 $0$。那么只需考虑合数部分。
还是像Min25筛的套路，枚举最小的质因子 $P_k$ 以及他的幂次 $q$，如果此时这个质因子不是次大的质因子，那么贡献就是 $S(\frac{n}{P_k^q},k+1)$，否则就是 $P_k$ 乘上 $[1,\frac{n}{P_k^q}]$ 中的质数个数。
那么只需要预处理出所有形如 $\frac{n}{i}$ 的质数个数就好了。
这个用Min25的前半部分即可。
时间复杂度 $O(\frac{n^{\frac{3}{4}}}{\log n})$。
程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <iostream>
#include <cmath>
using namespace std;
#define ll long long
const int N=4e6;
int cnt;
ll pri[N];
bool vis[N];
inline void init(int n)
{
cnt=0;
for(int i=2;i<=n;i++) vis[i]=0;
for(int i=2;i<=n;i++)
{
if(!vis[i]) pri[++cnt]=i;
for(int j=1;j<=cnt&&1ll*pri[j]*i<=n;j++)
{
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
}
ll now_n,f[N],w[N];
int id1[N],id2[N];
int Sqr,m;
ll S(ll n,int j)
{
if(pri[j]>n||n<=1) return 0;
ll sum=0,tmp,x; int y;
for(int i=j;1ll*pri[i]*pri[i]<=n&&i<=cnt;i++)
{
tmp=pri[i];
for(int k=1;tmp*pri[i]<=n;tmp*=pri[i],k++)
{
x=n/tmp;
y=(x<=Sqr)?id1[x]:id2[now_n/x];
sum+=S(x,i+1)+1ll*pri[i]*(f[y]-(i-1));
}
}
return sum;
}
inline ll solve(ll n)
{
Sqr=sqrt(n); m=0;
for(ll i=1,j;i<=n;i=j+1)
{
j=n/(n/i);
w[++m]=n/i;
w[m]<=Sqr?id1[w[m]]=m:id2[n/w[m]]=m;
f[m]=w[m]-1;
}
ll x; int y;
for(int i=1;i<=cnt&&1ll*pri[i]*pri[i]<=n;i++)
{
for(int j=1;j<=m&&1ll*pri[i]*pri[i]<=w[j];j++)
{
x=w[j]/pri[i];
y=(x<=Sqr)?id1[x]:id2[n/x];
f[j]-=f[y]-(i-1);
}
}
now_n=n;
return S(n,1)+1;
}
ll l,r,ans;
int main()
{
cin>>l>>r;
init(sqrt(r));
cout<<solve(r)-solve(l-1);
return 0;
}
|