对于输入号码N , 我试图找到特殊对的数量 (x,y)满足以下条件:
-
x != y -
1 <= N <= 10^50 -
0 <= x <= N -
0 <= y <= N -
F(x) + F(y)是素数,其中F是数字所有数字的总和
最后打印计数模1000000007的输出
示例输入: 2
示例输出: 2
说明:
- (0,2) Since
F(0)+F(2)=2which is prime- (1,2) Since
F(1)+F(2)=3which is prime- (2,1) is not considered as (1,2) is same as (2,1)
我的代码是:
def mod(x,y,p):
res=1
x=x%p
while(y>0):
if((y&1)==1):
res=(res*x)%p
y=y>>1
x=(x*x)%p
return res
def sod(x):
a=str(x)
res=0
for i in range(len(a)):
res+=int(a[i])
return res
def prime(x):
p=0
if(x==1 or x==0):
return False
if(x==2):
return True
else:
for i in range(2,(x//2)+1):
if(x%i==0):
p+=1
if(p==0):
return (True)
else:
return(False)
n=int(input())
res=[]
for i in range (n+1):
for j in range(i,n+1):
if(prime(sod(int(i))+sod(int(j)))):
if([i,j]!=[j,i]):
if([j,i] not in res):
res.append([i,j])
count=len(res)
a=mod(count,1,(10**9)+7)
print(res)
print(a)
我期望 9997260736 的输出成为671653298但错误是代码执行超时。
请您参考如下方法:
已经发布了有点太长的评论,所以将其更改为回答:
在考虑此类问题时,不要将问题直接转化为代码,而是看看您只能做一次或以不同的顺序做些什么。
截至目前,您正在执行 N*N通过,每次计算 x 和 y 的数字总和(还不错)并分解每个总和以检查它是否为素数(真的很糟糕)。这意味着总和 s你在检查它是否是素数 s+1次! (对于 0+s、1+(s-1)、...、(s-1)+1、s+0)。
您可以做什么不同的事情?
让我们看看我们知道什么:
许多数字的数字总和是相同的。
对于许多值,sod(x) 和 sod(y) 的总和是相同的。
数字在其第一次和第 n 次检查期间为质数(并且检查它是否为质数的成本很高)。
所以最好只计算一次质数,并且每个和只计算一次。但是当我们有很多数字时该怎么做呢?
换个思路:得到质数,将其拆分为两个数(sodx和sody),然后从这些数生成x和y。
例子:
总理 p = 7 .给出可能的总和为 0+7、1+6、2+5、3+4。
然后对于每个总和,您可以生成一个数字,例如对于 N=101 和 sod=1,您有 1、10、100,对于 sod=2,您有 2、11、20、101。您可以存储它,但生成它应该不会那么糟糕。
其他优化:
你必须考虑如何使用你的 N 来限制生成质数:
给定 N 的 lenN 个数字(记住,lenN 是 ~log(N)),可能的最大数字和是 9*lenN(对于仅由 9 组成的 N)。这意味着我们的 sodx 和 sody <= 9*lenN,所以素数 p = sodx + sody <= 18*lenN
看:这意味着 18*lenN 检查数字是否为质数与 N*N 检查您以前的算法有!
