Специальные пары с суммой в качестве простого числа - PullRequest
Новая
       36

Специальные пары с суммой в качестве простого числа

2 голосов
/ 24 июня 2019

Число N дается в диапазоне 1 <= N <= 10^50.Функция F(x) определяется как сумма всех цифр числа x.Мы должны найти количество специальных пар (x, y), которое будет таким:1. 0 <= x, y <= N2. F(x) + F(y) прост в природеМы должны считать (x, y) и (y, x) только один раз.Вывести вывод по модулю 1000000000 + 7 Мой подход: Поскольку максимальное значение суммы цифр в заданном диапазоне может составлять 450 (если все символы равны 9, то их длина равна 50, что дает 9*50 = 450).Таким образом, мы можем создать двумерный массив размером 451 * 451 и для всей пары мы можем сохранить, является ли он простым или нет.Теперь проблема, с которой я сталкиваюсь, состоит в том, чтобы найти все пары (x, y) для заданного числа N за линейное время (очевидно, мы не можем перебрать 10 ^ 50, чтобы найти все пары).Может ли кто-нибудь предложить какой-либо подход или любую формулу (если она существует), чтобы получить все пары за линейное время.

1 Ответ

0 голосов
/ 24 июня 2019

Вы можете создать двумерный массив размером 451 * 451, и для всей пары мы можем сохранить, простое оно или нет.В то же время, если вы знаете, сколько чисел меньше n, у которых F (x) = i, а сколько F (x) = j, то после проверки (i + j) простое число или нет, вы можете легко найти результатс состоянием (i, j) двумерного массива размером 451 * 451.

Итак, вам нужно найти общее число, для которого F (x) = i.

Вы можете легко сделать это, используя цифру dp:

Цифра 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;
}

Эта функция будет возвращать итоговые числа, меньшие чем n, у которых F (x) = i.

Таким образом, мы можем вызвать эту функцию для каждого i от 0 до 451 и сохранить результат во временной переменной. 

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.
...