SPOJ DIVCNT3 - Counting Divisors (cube)

[传送门](https://www.spoj.com/problems/DIVCNT3/)
题意：计算$\sigma_0(i^3)$的前缀和

以前雅礼集训的时候就听说过这题，好像是洲阁筛板子？

但是如今世道不同了，$Min\_25$筛可以把这种东西吊起来筛！

当$p\in Prime,f(p^c)=3c+1$
因此，当$p\in Prime,f(p)=4$
并且常函数$g(n)=4$的前缀和为$4n$可以$O(1)$计算。

于是$Min\_25$筛就可以了，复杂度$O(10^{11})$能过

```
#include<cstdio>
#include<iostream>
#include<cmath>
#define LL long long
using namespace std;
LL rn; 
int B, pri[1000005], vis[1000005];
void pre(int N) {
	vis[1] = 1;
	for(register int i = 2; i <= N; ++i) {
		if(!vis[i]) pri[++(*pri)] = i;
		for(register int j = 1; j <= (*pri) && i * pri[j] <= N; ++j) {
			vis[i * pri[j]] = 1;
			if(i % pri[j] == 0) break;
		}
	}
	//pri[N] = 1e9;
}

LL w[1000005], g[1000005];
int id1[1000005], id2[1000005];

LL GetG(LL n) {
	LL k; int m = 0;
	for(register LL l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		k = n / l, w[++m] = k;
		if(k <= B) id1[k] = m;
		else id2[n / k] = m;
		g[m] = w[m] - 1;
	}
	for(register int i = 1; i <= *pri; ++i) {
		for(register int j = 1; j <= m && 1ll * pri[i] * pri[i] <= w[j]; ++j) {
			k = w[j] / pri[i];
			int d = (k <= B) ? id1[k] : id2[n / k];
			g[j] = g[j] - g[d] + i - 1;
		}
	}
}

LL S(LL n, int m) {
	if(n <= 1ll || pri[m] > n) return 0;
	int k = (n <= B) ? id1[n] : id2[rn / n];
	LL ans = 4ll * (g[k] - (m - 1)), x1, x2;
	for(register int i = m; i <= *pri && 1ll * pri[i] * pri[i] <= n; ++i) {
		x1 = pri[i], x2 = 1ll * pri[i] * pri[i];
		for(register int p = 1; x2 <= n; ++p, x1 = x2, x2 *= pri[i]) {
			ans += (3 * p + 1) * S(n / x1, i + 1) + 3 * (p + 1) + 1;
		}
	}
	return ans;
}

int main() {
	int t;
	pre(1000005);
	scanf("%d", &t);
	while(t--) {
		scanf("%lld", &rn);
		B = (int)sqrt(rn) + 1;
		GetG(rn);
		printf("%lld\n", S(rn, 1) + 1);
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链