2

对于输入 number 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) 因为F(0)+F(2)=2哪个是素数
  • (1,2) 因为F(1)+F(2)=3哪个是素数
  • (2,1) 不被视为 (1,2) 与 (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但错误是代码执行超时。

4

1 回答 1

1

已经发表了有点太长的评论，所以改变它来回答：

考虑此类问题时，不要将问题直接转化为代码，而是看看你能做一次或以不同的顺序做什么。

到目前为止，您正在做N*N通过，每次计算 x 和 y 的数字总和（不是那么糟糕）并分解每个总和以检查它是否是素数（真的很糟糕）。这意味着总而言之s，您正在检查它是否是黄金s+1时段！（对于 0+s、1+(s-1)、...、(s-1)+1、s+0）。

你可以做些什么不同的事情？

让我们看看我们知道什么：

  • 许多数字的数字总和是相同的。

  • sod(x) 和 sod(y) 的总和对于许多值是相同的。

  • Number 在第 1 次和第 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 限制生成素数：

给定具有 lenN 个数字的 N（请记住，lenN 是 ~log(N)），可能的最大数字总和是 9*lenN（对于仅由 9 组成的 N）。这意味着我们的 sodx 和 sody <= 9*lenN，所以素数p = sodx + sody <= 18*lenN

看：这意味着 18*lenN 检查数字是否为素数，而 N*N 检查您以前的算法！

于 2019-07-18T12:52:33.313 回答