以总和为素数的特殊对 [英] Special Pairs with sum as Prime Number

问题描述

在范围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(如果所有字符均为9，且长度为50，则给出9*50 = 450).因此，我们可以创建一个大小为451 * 451的二维数组，并且可以存储所有对的素数.
现在，我面临的问题是在线性时间内找到给定数字N的所有对(x，y)(很显然，我们无法循环通过10 ^ 50来找到所有对.有人可以建议任何方法或任何公式(如果存在)以线性时间获取所有对.

A number N is given in the range 1 <= N <= 10^50. A function F(x) is defined as the sum of all digits of a number x. We have to find the count of number of special pairs (x, y) such that:
1. 0 <= x, y <= N
2. F(x) + F(y) is prime in nature
We have to count (x, y) and (y, x) only once. Print the output modulo 1000000000 + 7

My approach:
Since the maximum value of sum of digits in given range can be 450 (If all the characters are 9 in a number of length 50, which gives 9*50 = 450). So, we can create a 2-D array of size 451*451 and for all pair we can store whether it is prime or not.
Now, the issue I am facing is to find all the pairs (x, y) for given number N in linear time (Obviously, we cannot loop through 10^50 to find all the pairs). Can someone suggest any approach, or any formula (if exists), to get all the pairs in linear time.

推荐答案

您可以创建大小为451 * 451的二维数组，对于所有对，我们都可以存储它是否为质数.同时，如果您知道有多少小于n的F(x)= i和多少有F(x)= j，那么在检查(i + j)为素数之后，您可以轻松地找到结果大小为451 * 451的二维数组的状态(i，j).

You can create a 2-D array of size 451*451 and for all pair we can store whether it is prime or not. At the same time if you know how many numbers less than n who have F(x)=i and how many have F(x)=j, then after checking (i+j) is prime or not you can easily find a result with the state (i,j) of 2-D array of size 451*451.

因此，您需要查找具有F(x)= i的总数.

So what you need is finding the total numbers who have F(x) =i.

您可以使用数字dp轻松完成此操作:

You can easily do it using digit dp:

数字DP，用于查找具有F(x)= i的数字:

Digit DP for finding how many numbers who have 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;
}

此函数将返回F(x)= i小于n的总数.

This function will return the total numbers less than n who have F(x)=i.

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

So we can call this function for every i from 0 to 451 and can store the result in a temporary variable.

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

现在对每对(i，j)进行测试:

Now test for each pair (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)将被计算一次.

finally result will be answer/2 as (i,j) and (j,i) will be calculated once.

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

这篇关于以总和为素数的特殊对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！