和为质数的特殊对

Question

在 1 <= N <= 10^50 范围内给出了一个数字 N。函数 F(x) 被定义为数字 x 的所有数字的总和。我们必须找到特殊对 (x, y) 的数量，使得：
1. 0 <= x, y <= N
2. F(x) + F(y)本质上是质数
我们只需要计算 (x, y) 和 (y, x) 一次。打印输出模 1000000000 + 7

我的做法：
由于给定范围内的数字和的最大值可以是 450（如果长度为 50 的数字中的所有字符都是 9，则给出 9*50 = 450）。因此，我们可以创建一个大小为 451*451 的二维数组，并且对于所有对，我们可以存储它是否为质数。
现在，我面临的问题是在线性时间内找到给定数字 N 的所有对 (x, y)（显然，我们不能通过 10^50 循环来找到所有对）。有人可以建议任何方法或任何公式（如果存在），以在线性时间内获得所有对。

Answer 1

您可以创建一个大小为 451*451 的二维数组，对于所有对，我们可以存储它是否为素数。同时如果你知道有多少个小于n的数有F(x)=i，有多少个有F(x)=j，那么在检查(i+j)是否为素数后你可以很容易地找到一个结果具有大小为 451*451 的二维数组的状态 (i,j)。

所以你需要的是找到 F(x) =i 的总数。

您可以使用数字 dp 轻松完成：

Digit DP 用于查找有多少个数字有 F(x)=i:

string given=convertIntToString(given string);
int DP[51][2][452]= {-1};
Initially all index hpolds -1;
int digitDp(int pos,int small,int sum)
{
    if(pos==given.size())
    {
        if(sum==i) return 1;
        else return 0;
    }
    if(DP[pos][small][sum]!=-1)return DP[pos][small][sum];
    int res=0;
    if(small)
    {
        for(int j=0; j<=9; j++)res=(res+digitDp(pos+1,small,sum+j))%1000000007;
    }
    else
    {
        int hi=given[pos]-'0';
        for(int j=0; j<=hi; j++)
        {
            if(j==hi)res=(res+digitDp(pos+1,small,sum+j))%1000000007;
            else res=(res+digitDp(pos+1,1,sum+j))%1000000007;
        }
    }
    return DP[pos][small][sum]=res;
}

此函数将return 小于n 且F(x)=i 的总数。

所以我们可以为从 0 到 451 的每个 i 调用这个函数，并将结果存储在一个临时变量中。

int res[452];
for(i=0;i<=451;i++){
  memset(DP,-1,sizeof DP);
  res[i]=digitDp(0,0,0);
}

现在测试每对 (i,j) :

int answer=0;
for(k=0;k<=451;k++){
   for(int j=0;j<=451;j++){
       if(isprime(k+j)){
         answer=((log long)answer+(long long)res[k]*(long long)res[j])%1000000007;
      }
   }
}

最终结果将是 answer/2，因为 (i,j) 和 (j,i) 将计算一次。

Although there is a case for i=1 and j=1 , Hope you will be able to  handle it.

Answer 2

这是 Python 中的答案，如果这样可以使代码更易于阅读和理解。

primes = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997])
DP = []
given = ''
k = 0

def memset():
    global DP
    DP = [[[-1 for k in range(452)] for j in range(2)] for i in range(51)]

def digitDp(pos , small , final):
    global DP , k
    if pos == len(given):
        if final == k:
            return 1
        else:
            return 0

    if DP[pos][small][final] != -1:
        return DP[pos][small][final]

    res = 0
    if small:
        for i in range(10):
            res=(res+digitDp(pos+1,small,final+i))% 1000000007
    else:
        hi = int(given[pos]) - 0
       
        for i in range(hi+1):
            if(i == hi):
                 res= (res + digitDp(pos + 1 , small, final + i)) % 1000000007
            else:
                 res = (res + digitDp(pos + 1 , 1 , final + i)) % 1000000007

    DP[pos][small][final] = res
    return DP[pos][small][final]


def main():
    result = [0] * 452
    global primes , k , given

    given = str(input())
    for k in range(452):
        memset()
        result[k] = digitDp(0 , 0 , 0)
  
    answer = 0
    for i in range(452):
        for j in range(452):
            if (i+j) in primes:
                 answer = (answer + result[i] * result[j]) % 1000000007
    print(answer // 2)

main()

感谢@mahbubcseju 提供了这个问题的解决方案。

和为质数的特殊对

Special Pairs with sum as Prime Number

algorithm

math

primes

dynamic-programming