【题解】SPOJ数个数

题目名称是我瞎写的233

事实上是 $\rm SPOJ$ 的三倍经验道题,解决的是以下问题:

其中 $n,k$ 给定,$n\leq 10^{10},\quad k\leq2^{64}$

我也忘了是不是这个数据范围反正能过就对了

提交链接 :

1 $k=2$ DIVCNTK2
2 $k=3$ DIVCNTK3
3 $\mathrm{input} ~k$ DIVTNK(general)

正经题解

其实很水的,对吧?已知 $\forall p\in \mathbb{P,}~\sigma_0(p^k)=k+1$,所以有 $f(p)=k+1,f(p^j)=jk+1$ 于是这东西看起来可以效仿原来的思路直接设一个 $f(p)=1,f(p)=k$ 来做,然后就。。。就不对了!

然后我就很奇怪啊,为啥按照公式推,$g$ 应该没推错,但是结果不对?迷惑了大半个上午。

…到最后这个题纠结了半天,原因是我忘了 $f(p)=k$ 这东西 不是积性函数 ,所以不能去推 $f(k)$,也就是说不能直接拆

然后为了这个事儿还去 uoj 群丢了一上午人,Life so hard ….

所以怎么解决?考虑只维护一个 $f(p)=1$,然后计算的时候 $\times ~(k+1)$ 就完了。

最后还是 iostream 神仙在Luogu的讨论区帮了我,十分感动555

总结:感觉自己是个弟弟qaq

然后以下是正确写法,只推一个 $h$ 就好了。

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
LL n, e ;
LL val[N], h[N] ;
int s, tot, cnt ;
LL id1[N], id2[N] ;
int T, chk[N], pr[N] ;
const LL Inv2 = 500000004 ;

void sieve(int m){
chk[0] = chk[1] = 1 ;
for (int i = 2 ; i <= m ; ++ i){
if (!chk[i])
pr[++ cnt] = i ;
for (int j = 1 ; j <= cnt ; ++ j){
if (i * pr[j] > m) break ;
chk[i * pr[j]] = 1 ;
if (i % pr[j] == 0) break ;
}
}
}
LL S(LL p, int q){
if (pr[q] >= p) return 0 ;
LL id = p <= s ? id1[p] : id2[n / p] ;
LL ans = h[id] * (e + 1) - q * (e + 1);
for (int k = q + 1 ; k <= cnt ; ++ k){
if (1ll * pr[k] * pr[k] > p)
break ; LL m = pr[k], t = pr[k] ; int o ;
for (o = 1 ; m <= p ; ++ o, m *= t)
ans += 1ull * (o * e + 1) * (S(p / m, k) + (o > 1)) ;
}
return ans ;
}
int main(){
cin >> T ;
sieve(N - 1) ;
LL l, r, w, t ;
while (T --){
cin >> n, e = 3 ;
s = sqrt(n) ; tot = 0 ;
for (l = 1 ; l <= n ; l = r + 1){
t = n / l ; r = n / t ;
val[++ tot] = t ; h[tot] = t - 1 ;
if (t <= s) id1[t] = tot ; else id2[l] = tot ;
}
for (int i = 1 ; i <= cnt ; ++ i){
LL nowp = 1ll * pr[i] * pr[i], w, id ;
if (nowp > n) break ;
for (int j = 1 ; j <= tot && val[j] >= nowp ; ++ j){
w = val[j] / pr[i] ;
id = (w <= s) ? id1[w] : id2[n / w] ;
h[j] -= h[id] - (i - 1) ;
}
}
cout << S(n, 0) + 1 << '\n' ;
}
}

彩蛋

上午在去 uoj 群里丢脸之前,找到欧神 ouuuyuuu (欧神:说了多少遍我不打算起这个ID!?)——我校现役MO最强战力,SD-01,CMO2019非集训队第一。找他是因为曾经给他看过杜教筛,他觉得简单,于是我就让他现场 $5min$ 学完了 $\rm Min25$ 筛(可能效果不是很好)然后问他为什么不对。

然后我俩:

好迷啊(齐声)

所以事实证明,弱菜弱到一定地步是可以带飞神仙的。qed。