SPOJ DIVCNTK - Counting Divisors (general)

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

一道牛逼题目，$Min\_25$筛写的很简短。

当$p\in Prime,f(p^c)=ck+1$
且当$p\in Prime,f(p)=k+1$
又因为前缀和$\sum^n_{i=1}k+1=n(k+1)$可以$O(1)$

直接$Min\_25$筛就行了，复杂度$O(10^{11})$能过。

```
#include<cstdio>
#include<algorithm>
#define LL unsigned long long
#define ui unsigned int
using namespace std;
const int maxn = 5e6;
LL rn, k;
ui pri[maxn + 5], vis[maxn + 5], B, t;
void pre(int N) {
	vis[1] = 1;
	for(register int i = 2; i <= N + 2; ++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;
		}
	}
}

LL g[maxn + 5], w[maxn + 5];
ui id1[maxn + 5], id2[maxn + 5];
void GetG(LL n) {
	LL k; ui m = 0;
	for(register LL l = 1, r; l <= rn; 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] = k - 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];
			ui d = (k <= B) ? id1[k] : id2[n / k];
			g[j] = g[j] - g[d] + (i - 1);
		}
}

inline LL F(int c) {
	return 1ll * c * k + 1;
}

LL S(LL n, int m) {
	if(n <= 1ll || pri[m] > n) return 0;
	ui d = (n <= B) ? id1[n] : id2[rn / n];
	LL ans = 1ll * (k + 1) * (g[d] - (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 += F(p) * S(n / x1, i + 1) + F(p + 1);
	}
	return ans;
}

int main() {
	scanf("%d", &t);
	pre(500000);
	while(t--) {
		scanf("%llu%llu", &rn, &k);
		for(B = 1; 1ll * B * B <= rn; ++B);
		GetG(rn);
		printf("%llu\n", S(rn, 1) + 1);
	}
	return 0;
} 
```

Rockdu's Blog

导航

最近发表

大佬们的友链