Project Euler 580 Squarefree Hilbert numbers

前几天在UOJ群里看到有人问这道题...发现好像会做的样子就去看了一下...是一道很有意思的题呢。

题目大意

H={4k+1∣k≥0}H = \{4k+1\mid k\ge 0\}H={4k+1k0} 为 Hilbert numbers。对于整数 x∈Hx\in HxH,如果不存在d∈Hd\in HdHd>1d>1d>1,使得 d2∣xd^2\mid xd2x,则称 xxx 为 squarefree Hilbert number。求不超过 nnn 的 squarefree Hilbert number 的个数。

在本题中,n=1016n=10^{16}n=1016

题目链接

Project Euler 580

题解

我们先回顾一个经典问题:求不超过 nnn 的无平方因子的数的个数。这里称正整数 xxx 是无平方因子的当且仅当不存在 d∈Zd\in \mathbb{Z}dZ 使得 d2∣xd^2\mid xd2x

这个问题可以很简单的使用容斥原理来解决。记 AAA 为无平方因子的数构成的集合,f(i)=∣{x∣x≤n,i2∣x,xi2∈A}∣f(i)=\left|\left\{x\mid x\le n,i^2\mid x ,\frac{x}{i^2}\in A\right\}\right|f(i)={xxn,i2x,i2xA}g(i)=∣{x∣x≤n,i2∣x}∣g(i)=\left|\left\{x\mid x\le n,i^2\mid x\right\}\right|g(i)={xxn,i2x}。显然,仅当 i2≤ni^2\le ni2n 时才可能有 f(i)≠0f(i)\ne0f(i)0g(i)≠0g(i)\ne0g(i)0,且 g(i)=⌊ni2⌋g(i)=\left\lfloor\frac{n}{i^2}\right\rfloorg(i)=i2n。观察可以发现,f(i)f(i)f(i)g(i)g(i)g(i) 之间存在以下关系:

g(i)=∑kf(ki)g(i)=\sum_kf(ki)g(i)=kf(ki)

如果我们沿 iii 从大到小的的顺序计算 f(i)f(i)f(i),则可以通过枚举倍数的方法在 O(n1/2logn)O\left(n^{1/2}\log n\right)O(n1/2logn) 时间内计算出所有的 f(i)f(i)f(i)。答案即为 f(1)f(1)f(1)

很容易想到,对于原题,能否也用类似的做法解决呢?容易发现对于 x,y∈Hx, y\in Hx,yH,有xy∈Hxy\in HxyH。那么如果对于 i∈Hi\in HiH,类似的定义 f(i)f(i)f(i)g(i)g(i)g(i)…很可惜的是,通过计算可以得到,利用同样方法容斥得到的答案并不正确。一定是 f(i)f(i)f(i)g(i)g(i)g(i) 的关系出现了错误。问题出在哪里呢?

通过思考,可以发现一个事实:唯一分解定理在 HHH 中并不成立。考虑数 3×7×11×19=21×209=33×1333\times7\times11\times19=21\times209=33\times1333×7×11×19=21×209=33×133,而 21,209,33,13321,209,33,13321,209,33,133 均为 HHH 中的不可约数。这就导致了比如 34×72=92×49=212×93^4\times7^2=9^2\times49=21^2\times934×72=92×49=212×9 会在 f(9)f(9)f(9)f(21)f(21)f(21) 中重复计算,破坏了之前的做法利用容斥原理的性质。怎么处理这个问题呢?

聪明的你一定已经想到了,如果不仅仅考虑 HHH 而考虑所有奇数所构成的集合,则唯一分解定理仍然是成立的。因此,如果我们对所有奇数 iii 定义 f(i)f(i)f(i)g(i)g(i)g(i),则仍然可以用容斥计算 f(i)f(i)f(i)。然而这时的 f(1)f(1)f(1) 并不是答案,答案是什么呢?

这时的答案是:

f(1)+i=4k+3,i is primef(i)

正确性留给读者思考。(才不是我懒得写了呢)

于是我们得到了一个 O(n1/2logn)O\left(n^{1/2}\log n\right)O(n1/2logn) 的做法,在本机跑较短时间就能得出结果。

发表评论

电子邮件地址不会被公开。 必填项已用*标注