Calculate in [L, R] how many numbers whose sum of digits and sum of squares of digits are primes ?

Блог пользователя turbozone88

Автор turbozone88, история, 19 месяцев назад, По-английски

Calculate in [L, R] how many numbers whose sum of digits and sum of squares of digits are primes ?

Limit :

* 1 <= L <= R <= 10 ^ 18

* T <= 10 ^ 4: is the number of queries [L, R].

For example, in the [1, 20] there are 4 numbers which are 11, 12, 14, 16.

turbozone88
19 месяцев назад
22

Комментарии (17)

Показать архивные | Написать комментарий?

Mapegz

19 месяцев назад, # |

-31

This code might help! Let me know if it works

/*******************************************************************************
////////////////////////////////////////////////////////////////////////////////
||                                                                            ||
||  _____           _       ______        ___  ___                            ||
|| /  __ \         | |      | ___ \       |  \/  |                            ||
|| | /  \/ ___   __| | ___  | |_/ /_   _  | .  . | __ _ _ __   ___  __ _ ____ ||
|| | |    / _ \ / _` |/ _ \ | ___ \ | | | | |\/| |/ _` | '_ \ / _ \/ _` |_  / ||
|| | \__/\ (_) | (_| |  __/ | |_/ / |_| | | |  | | (_| | |_) |  __/ (_| |/ /  ||
||  \____/\___/ \__,_|\___| \____/ \__, | \_|  |_/\__,_| .__/ \___|\__, /___| ||
||                                |___/                |_|         |___/      ||
||                                                                            ||
////////////////////////////////////////////////////////////////////////////////
********************************************************************************/

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <ctype.h>
#define ll long long 
using namespace std;

//checking if prime
bool isPrime(ll n) {
    if (n<=1) return false;
    for (ll i=2; i<n; i++) 
        if (n%i==0) return false;
    return true;
}

//finding sum of digits of number, and sum of square of digits!
vector<ll> sod(ll n) {
    ll sum = 0, psum = 0;
    for (;n!=0;n/=10) {
        sum += n%10;
        psum += (n%10)*(n%10);
    }
    vector<ll> result;
    result.push_back(sum);
    result.push_back(psum);
    return result;
}

int main() {
    ll l,r;
    cin >> l >> r;
    //final loop to check all numbers in range
    for (ll i=l; i<=r;i++) {
        vector<ll> v = sod(i);
        if(isPrime(v[0]) && isPrime(v[1])) cout << i << " ";
    }
    return 0;
}

→ Ответить

SashaT9

19 месяцев назад, # ^ |

$$$1 \le l,r \le 10^{18}$$$

→ Ответить

vitosevskich

19 месяцев назад, # ^ |

Your code doesn't work. It would get TLE because you are iterating over the whole range $$$[L,R]$$$ which can have length up to $$$10$$$^$$$18$$$.

Note: it is also possible to check if number is prime in $$$O(sqrt(n))$$$.

→ Ответить

Dan4Life

19 месяцев назад, # |

Learn Digit DP

→ Ответить

k1r1t0

19 месяцев назад, # ^ |

← Rev. 2 →

-15

→ Ответить

turbozone88

19 месяцев назад, # ^ |

I code digit dp for each query and TLE

→ Ответить

k1r1t0

19 месяцев назад, # ^ |

← Rev. 2 →

-15

→ Ответить

BF_OF_Priety

19 месяцев назад, # ^ |

I think digit can pass easily if you smartly handle states, even naive digit dp will pass too I guess

→ Ответить

Dan4Life

19 месяцев назад, # ^ |

← Rev. 3 →

+12

$$$dp[i][j][k][l]$$$ = first i numbers, j(0/1) determines <= target number, k is the current sum of digits, l is current sum of square digits

There are only actually 18*2*9*18*81*18 = 8,503,056 possible states regardless of T

UPD: You might be wondering: How to do this without having the reset dp array every time? There's a neat trick that allows for resetting dp only once at the start, by reversing the numbers and doing the dp from right to left instead.

→ Ответить