[BZOJ 5455] [SPOJ 20173] DIVCNT2

87 阅读 0 评论 58 点赞

我是靠谱客的博主虚拟香烟，这篇文章主要介绍[BZOJ 5455] [SPOJ 20173] DIVCNT2，现在分享给大家，希望可以做个参考。

洛谷传送门

SPOJ传送门

BZOJ传送门

注： $B Z O J$ 数据范围稍有不同，博主程序以 $B Z O J$ 为标准~~实际上是在SPOJ上面卡不过QAQ~~

Description

Input

第一行一个自然数 $T$ 表示数据组数

下接 $T$ 行，每行一个正整数 $n$

$T ≤ 10, n ≤ 10^9$

Output

输出 $T$ 行，每行一个数字表示答案

Sample Input

复制代码

Sample Output

复制代码

1
2
3
4
5
14145459
191698371
2494643347
31475021381

解题分析

上次在这道题中我们分析出了一个 $sigma_0(i)$ 的性质，这里还需要用到一个：
$sigma_0(n^2)=sum_{i|n}2^{omega(i)}$
其中 $ω (n)$ 表示 $n$ 的不同质因数的个数。

仍然考虑将 $n$ 分解为 $n=p_1^{a_1}*p_2^{a_2}*p_3^{a_3}*......*p_k^{a_k}$ ，那么对于每个原有的约数 $m$ ，那么我们可以让任何一个质数次幂 $a_i$ 得到一个新的组合，而这样枚举恰好是覆盖了所有情况的。

注意到 $2^{omega(n)}$ 还有一个意义： $n$ 的不含平方因子的约数个数。

因此实际上 $2^{w(n)}=sum_{d|n}mu^2(d)$ 。

所以我们可以设 $f(x)=sigma_0(x^2)$ ， $g(x)=2^{omega(x)}$ ， $h(x)=mu^2(x)$ ，那么有
$\ g(x)=h(x)*I(x) \ f(x)=h(x)*I(x)*I(x) \ =h(x)*(I(x)*I(x)) \ =h(x)*sigma_0(x)$
所以就有
$sum_{i=1}^nf(x) \ =sum_{i=1}^nmu^2(i)sum_{j=1}^{lfloorfrac{n}{i}rfloor}sigma_0(j)$
而这两个函数也可以在 $N$ 的时间内筛出来：
$sum_{i=1}^nmu^2(i)=sum_{i=1}^{sqrt n}mu(i)lfloorfrac{n}{i^2}rfloor \ sum_{i=1}^nsigma_0(i)=sum_{i=1}^{n}lfloorfrac{n}{i}rfloor$

然后可以类似杜教筛，处理出前 $N^frac{2}{3}$ 项，使得总复杂度在下底分块后达到 $O(N^frac{2}{3})$ 。

代码如下：

复制代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <bitset>
#include <cstdlib>
#include <tr1/unordered_map>
#include <map>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 1000050
#define ll long long
template <class T>
IN void in(T &x)
{
x = 0; R char c = gc;
for (; !isdigit(c); c = gc);
for (;
isdigit(c); c = gc)
x = (x << 1) + (x << 3) + c - 48;
}
int pcnt;
short miu[MX], cnt[MX];
int sgm0[MX], sum1[MX], pri[MX / 10], sum2[MX];
bool npr[MX];
std::tr1::unordered_map <ll, ll> mp1, mp2;
IN void get()
{
miu[1] = sgm0[1] = 1;
R int i, j, tar;
for (i = 2; i <= 1e6; ++i)
{
if (!npr[i]) miu[i] = -1, sgm0[i] = 2, pri[++pcnt] = i, cnt[i] = 1;
for (j = 1; j <= pcnt; ++j)
{
tar = i * pri[j];
if (tar > 1e6) break;
npr[tar] = true;
if (!(i % pri[j]))
{
miu[tar] = 0;
sgm0[tar] = sgm0[i] / (cnt[i] + 1) * (cnt[i] + 2);
cnt[tar] = cnt[i] + 1;
break;
}
miu[tar] = -miu[i];
sgm0[tar] = sgm0[i] << 1;
cnt[tar] = 1;
}
}
for (R int i = 1; i <= 1e6; ++i)
{
sum1[i] = sum1[i - 1] + (miu[i] != 0);
sum2[i] = sum2[i - 1] + sgm0[i];
}
}
IN ll solve1(R ll pos)//for sigma mu(i)^2
{
if (pos <= 1e6) return sum1[pos];
if (mp1.count(pos)) return mp1[pos];
ll bd = std::sqrt(pos);
ll ret = 0;
for (R ll i = 1; i <= bd; ++i) ret += miu[i] * (pos / (i * i));
return mp1[pos] = ret;
}
IN ll solve2(R ll pos)//for sigma sig0(i)
{
if (pos <= 1e6) return sum2[pos];
if (mp2.count(pos)) return mp2[pos];
ll ret = 0;
for (R ll lef = 1, rig; lef <= pos; lef = rig + 1)
{
rig = pos / (pos / lef);
ret += (pos / lef) * (rig - lef + 1);
}
return mp2[pos] = ret;
}
int main(void)
{
int T;
ll n, ans;
in(T); get();
W (T--)
{
in(n); ans = 0;
for (ll lef = 1, rig; lef <= n; lef = rig + 1)
{
rig = n / (n / lef);
ans += (solve1(rig) - solve1(lef - 1)) * solve2(n / lef);
}
printf("%lldn", ans);
}
}

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <bitset>
#include <cstdlib>
#include <tr1/unordered_map>
#include <map>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 1000050
#define ll long long
template <class T>
IN void in(T &x)
{
x = 0; R char c = gc;
for (; !isdigit(c); c = gc);
for (;
isdigit(c); c = gc)
x = (x << 1) + (x << 3) + c - 48;
}
int pcnt;
short miu[MX], cnt[MX];
int sgm0[MX], sum1[MX], pri[MX / 10], sum2[MX];
bool npr[MX];
std::tr1::unordered_map <ll, ll> mp1, mp2;
IN void get()
{
miu[1] = sgm0[1] = 1;
R int i, j, tar;
for (i = 2; i <= 1e6; ++i)
{
if (!npr[i]) miu[i] = -1, sgm0[i] = 2, pri[++pcnt] = i, cnt[i] = 1;
for (j = 1; j <= pcnt; ++j)
{
tar = i * pri[j];
if (tar > 1e6) break;
npr[tar] = true;
if (!(i % pri[j]))
{
miu[tar] = 0;
sgm0[tar] = sgm0[i] / (cnt[i] + 1) * (cnt[i] + 2);
cnt[tar] = cnt[i] + 1;
break;
}
miu[tar] = -miu[i];
sgm0[tar] = sgm0[i] << 1;
cnt[tar] = 1;
}
}
for (R int i = 1; i <= 1e6; ++i)
{
sum1[i] = sum1[i - 1] + (miu[i] != 0);
sum2[i] = sum2[i - 1] + sgm0[i];
}
}
IN ll solve1(R ll pos)//for sigma mu(i)^2
{
if (pos <= 1e6) return sum1[pos];
if (mp1.count(pos)) return mp1[pos];
ll bd = std::sqrt(pos);
ll ret = 0;
for (R ll i = 1; i <= bd; ++i) ret += miu[i] * (pos / (i * i));
return mp1[pos] = ret;
}
IN ll solve2(R ll pos)//for sigma sig0(i)
{
if (pos <= 1e6) return sum2[pos];
if (mp2.count(pos)) return mp2[pos];
ll ret = 0;
for (R ll lef = 1, rig; lef <= pos; lef = rig + 1)
{
rig = pos / (pos / lef);
ret += (pos / lef) * (rig - lef + 1);
}
return mp2[pos] = ret;
}
int main(void)
{
int T;
ll n, ans;
in(T); get();
W (T--)
{
in(n); ans = 0;
for (ll lef = 1, rig; lef <= n; lef = rig + 1)
{
rig = n / (n / lef);
ans += (solve1(rig) - solve1(lef - 1)) * solve2(n / lef);
}
printf("%lldn", ans);
}
}

最后

以上就是虚拟香烟最近收集整理的关于[BZOJ 5455] [SPOJ 20173] DIVCNT2的全部内容，更多相关[BZOJ内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：数学
浏览次数：87 次浏览
发布日期：2024-09-06 00:05:01
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_14_f2_12__23_g4.html

[BZOJ 5455] [SPOJ 20173] DIVCNT2

洛谷传送门

SPOJ传送门

BZOJ传送门

Description

Input

Output

Sample Input

Sample Output

解题分析

最后

评论列表共有 0 条评论

发表评论取消回复

[BZOJ 5455] [SPOJ 20173] DIVCNT2

洛谷传送门

SPOJ传送门

BZOJ传送门

Description

Input

Output

Sample Input

Sample Output

解题分析

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复