Project Euler 694

Project Euler 694

题目

Cube-full Divisors

A positive integer n is considered cube-full, if for every prime p that divides n, so does p3. Note that 1 is considered cube-full.

Let s(n) be the function that counts the number of cube-full divisors of n. For example, 1, 8 and 16 are the three cube-full divisors of 16. Therefore, s(16)=3.

Let S(n) represent the summatory function of s(n), that is S(n)=i=1ns(i).

You are given S(16)=19, S(100)=126 and S(10000)=13344.

Find S(1018).

解决方案

N=1018,M=N4. 计算 S 时,我们考虑枚举每一个满立方数 w,那么它们在 N 以内出现的次数为 Nw.

通过考察 n 分解质因数 n=i=1kpiei 的每个 ei,可以发现每一个满立方数可以通过 x3y4z5不重不漏地表出,其中 x,y 是两个无平方因子数,并且 gcd(x,y)=1.

实现时,首先使用筛法将 M 以内的所有无平方因子数进行筛选出来。前两层循环分别枚举两个无平方因子数 z y。注意判断 gcd(z,y)=1 时,只需要判断 zy 是否为无平方因子数即可,接下来直接枚举 x,从而构造出一个满立方因子数 x3y4z5

代码

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
from itertools import count
from tools import int_sqrt

N = 10 ** 18
M = int(N ** (1 / 4))
square_free = [1] * (M + 1)
for i in range(2, int_sqrt(M) + 1):
k = i * i
for j in range(k, M + 1, k):
square_free[j] = 0
ans = 0
for z in count(1, 1):
z5 = z ** 5
if z ** 5 > N:
break
if square_free[z]:
for y in count(1, 1):
y4 = y ** 4
mul = y4 * z5
if mul > N:
break
if square_free[y] and square_free[z * y]:
for x in count(1, 1):
x3 = x ** 3
if mul * x3 > N:
break
ans += N // (mul * x3)
print(ans)

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝