以和为素数的特殊对

Question

数值N的范围为1<=N<=10^50。函数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)是否为素数后，你就可以很容易地找到一个状态为(i，j)的二维数组大小为451*451的结果。

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

您可以很容易地使用数字DP：

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;
}

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;
      }
   }
}

最后的结果将回答/2，因为（i,j）和（j,i）将被计算一次。

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