|
发表于 2017-9-13 05:24:44
|
显示全部楼层
好吧,出差也不忘记解个题
这题一开始看题目觉得很难,其实仔细推敲起来还可以,下面说说我的解题思路。
首先,当然要把复杂的概念化简,我们先看看NF(3,10000)的前几项是什么?
- T0=1
- N(3,0)=T0
- Nfac(3,0)=N(3,0)!=1!
- Nf(3,0)=0
- T1=1
- N(3,1)=T0+T1*3**1
- Nfac(3,1)=N(3,1)!=(T0+3*T1)!=4!=4*3*2*1
- Nf(3,1)=1
- T2=1
- N(3,2)=T0+T1*3**1+T2*3**2
- Nfac(3,2)=N(3,2)!=(T0+T1*3+3*T2*3)!=13!
- Nf(3,2)=13//3+4//3=5
- T3=2
- Nfac(3,3)=(T0+T1*3+3*3*T2+3*3*3*T3)!=(13+54)!=(67)!
- Nf(3,3)=67//3+22//3+7//3=22+7+2=31=(T1+3*T2+3*3*T3)+(T1+3*T2+3*3*T3)%3+((T1+3*T2+3*3*T3)%3)%3
复制代码
这题的难点其实是在算n阶乘中质数p的个数。从上面的展开项可以看到,n阶乘中p的个数可以用n反复整除p来计算。
于是,求解Nf(3,10000)就可以写成:
- S=290797
- T=[S%3]
- for i in range(10000):
- S=(S*S)%50515093
- T.append(S%3)
- q=0
- for i in range(1,10001):
- q += T[i]*3**(i-1)
- s = q % 3**20
- while q>=3:
- q //= 3
- s = (s+q) % 3**20
- print(s) # 624955285
复制代码
答案也是正确的,但是如果要求Nf(61,10**7)的话,上述的运算效率就比较慢了,不过我们可以借鉴上面这个的思路。
既然Nf(3,3)=67//3+22//3+7//3=22+7+2=31=(T1+3*T2+3*3*T3)+(T1+3*T2+3*3*T3)%3+((T1+3*T2+3*3*T3)%3)%3
那么我们是不是可以从内层开始逐渐往外层推呢?然后每层都可以取模运算,减小运算量。
于是Nf(61,10**7)就可以写成:
- S=290797
- T=[S%61]
- for i in range(10**7):
- S=(S*S)%50515093
- T.append(S%61)
- q=0
- s=0
- for i in range(10**7,0,-1):
- q = (q*61+T[i])%61**10
- s = (s+q)%61**10
- print(s) # 605857431263981935
复制代码
差不多9s可以出答案。
|
评分
-
查看全部评分
|