【SPOJ】DIVCNT2

56 阅读 0 评论 37 点赞

我是靠谱客的博主勤恳红酒，最近开发中收集的这篇文章主要介绍【SPOJ】DIVCNT2，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【题目链接】

点击打开链接

【思路要点】

Min25 M i n 25 筛模板题。
时间复杂度 O(N34LogN) O ( N 3 4 L o g N ) 。

【代码】


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 5;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
ull n, k, limit, val[MAXN], cnt[MAXN];
int m, tot, prime[MAXN], f[MAXN], home1[MAXN], home2[MAXN];
void init(int n) {
tot = 0;
for (int i = 2; i <= n; i++)
f[i] = 0;
for (int i = 2; i <= n; i++) {
if (f[i] == 0) prime[++tot] = f[i] = i;
for (int j = 1; j <= tot && prime[j] <= f[i]; j++) {
int tmp = prime[j] * i;
if (tmp > n) break;
f[tmp] = prime[j];
}
}
}
ull s(ull x, int y) {
if (x <= 1 || prime[y] > x) return 0;
ull ans = 0;
if (x <= limit) ans = cnt[home1[x]] - (y - 1);
else ans = cnt[home2[n / x]] - (y - 1);
ans *= k + 1;
for (int i = y; i <= tot && 1ull * prime[i] * prime[i] <= x; i++) {
ull now = prime[i], nxt = now * now;
for (int j = 1; nxt <= x; j++, now *= prime[i], nxt *= prime[i])
ans += s(x / now, i + 1) * (j * k + 1) + ((j + 1) * k + 1);
}
return ans;
}
int main() {
int T; read(T);
while (T--) {
read(n), k = 2;
limit = sqrt(n);
init(limit);
m = 0;
for (ull i = 1, nxt; i <= n; i = nxt) {
ull tmp = n / i;
nxt = n / tmp + 1;
val[++m] = tmp;
cnt[m] = tmp - 1;
if (tmp <= limit) home1[tmp] = m;
else home2[i] = m;
}
for (int i = 1; i <= tot; i++)
for (int j = 1; 1ull * prime[i] * prime[i] <= val[j]; j++) {
ull tmp = val[j] / prime[i];
if (tmp <= limit) cnt[j] -= cnt[home1[tmp]] - (i - 1);
else cnt[j] -= cnt[home2[n / tmp]] - (i - 1);
}
writeln(s(n, 1) + 1);
}
return 0;
}