欧拉计划773：Ruff 数

显示全部楼层 · 2012-5-21 10:19:41

本帖最后由〇〇于 2021-11-24 08:27 编辑
设Sk 是包含 2 和 5 以及以 7 结尾的前K个素数的集合。例如，S3={2,5,7,17,37} 。
将 K-Ruff 数定义为不能被 Sk中的任何元素整除的数。
如果Nk是Sk 中数字的乘积，则定义F(k)为小于最后一位数字 7 的所有 Ruff 数字的总和。
已知F(3)=76**452
求F(97)模1000000007，给出你的答案。

pe773.png (14.19 KB, 下载次数: 9)
下载附件
2021-11-24 08:17 上传

千问 · 2012-5-21 10:19:41

# 导入reduce
from functools import reduce
# 定义函数
def f(x,y):
return x*y
S3=[2,5,7,17,37]
def F(k):
Nk=reduce(f,S3)
s=0
for i in range(1,Nk):
a=1
for j in S3:
if i%j==0:
a=0
break
if i%10!=7:a=0
s+=a*i
return s

F(3)=761〇1452

千问 · 2012-5-21 10:19:41

其实最后一位是7，必然不能被2和5整除，其实相当于求分解质因数后不含末位7的因数的数字之和
对于F(3),被加的数的形式都是:
11^x1*13^x2*19^x3*23^x4*29^x5*31^x6
还要求最后一位是7，只能由3的幂贡献，1的幂是1，9的幂是1,9，

千问 · 2012-5-21 10:19:41

要得到末位7，可以是3的3、7、11次 *9的偶数次
或3的1、5、9次*9的奇数次

千问 · 2012-5-21 10:19:41

还要包括7结尾的质数