Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You should use DP for this task. Here is my solution:</p> <pre><code>#include &lt;stdio.h&gt; const int MAX_LENGTH = 18; const int MAX_SUM = 162; const int MAX_SQUARE_SUM = 1458; int primes[1459]; long long dyn_table[19][163][1459]; void gen_primes() { for (int i = 0; i &lt;= MAX_SQUARE_SUM; ++i) { primes[i] = 1; } primes[0] = primes[1] = 0; for (int i = 2; i * i &lt;= MAX_SQUARE_SUM; ++i) { if (!primes[i]) { continue; } for (int j = 2; i * j &lt;= MAX_SQUARE_SUM; ++j) { primes[i*j] = 0; } } } void gen_table() { for (int i = 0; i &lt;= MAX_LENGTH; ++i) { for (int j = 0; j &lt;= MAX_SUM; ++j) { for (int k = 0; k &lt;= MAX_SQUARE_SUM; ++k) { dyn_table[i][j][k] = 0; } } } dyn_table[0][0][0] = 1; for (int i = 0; i &lt; MAX_LENGTH; ++i) { for (int j = 0; j &lt;= 9 * i; ++j) { for (int k = 0; k &lt;= 9 * 9 * i; ++k) { for (int l = 0; l &lt; 10; ++l) { dyn_table[i + 1][j + l][k + l*l] += dyn_table[i][j][k]; } } } } } long long count_lucky (long long max) { long long result = 0; int len = 0; int split_max[MAX_LENGTH]; while (max) { split_max[len] = max % 10; max /= 10; ++len; } int sum = 0; int sq_sum = 0; for (int i = len-1; i &gt;= 0; --i) { long long step_result = 0; for (int l = 0; l &lt; split_max[i]; ++l) { for (int j = 0; j &lt;= 9 * i; ++j) { for (int k = 0; k &lt;= 9 * 9 * i; ++k) { if (primes[j + l + sum] &amp;&amp; primes[k + l*l + sq_sum]) { step_result += dyn_table[i][j][k]; } } } } result += step_result; sum += split_max[i]; sq_sum += split_max[i] * split_max[i]; } if (primes[sum] &amp;&amp; primes[sq_sum]) { ++result; } return result; } int main(int argc, char** argv) { gen_primes(); gen_table(); int cases = 0; scanf("%d", &amp;cases); for (int i = 0; i &lt; cases; ++i) { long long a, b; scanf("%lld %lld", &amp;a, &amp;b); printf("%lld\n", count_lucky(b) - count_lucky(a-1)); } return 0; } </code></pre> <p>Brief explanation:</p> <ul> <li>I'm calculating all primes up to 9 * 9 * MAX_LENGTH using Eratosthenes method;</li> <li>Later, using DP, I'm building table dyn_table where value <strong>X</strong> in <strong>dyn_table[i][j][k]</strong> means that we have exactly <strong>X</strong> numbers of length <strong>i</strong> with sum of digits equal to <strong>j</strong> and sum of its squares equal to <strong>k</strong></li> <li>Then we can easily count amount of lucky numbers from 1 to 999..999(<strong>len</strong> times of 9). For this we just sum up all <strong>dyn_table[len][j][k]</strong> where both <strong>j</strong> and <strong>k</strong> are primes.</li> <li>To calculate amount of lucky number from 1 to random <strong>X</strong> we split interval from 1 to <strong>X</strong> into intervals with length equal to 10^K (see *count_lucky* function).</li> <li>And our last step is subtract count_lucky(a-1) <em>(cause we are including <strong>a</strong> in our interval)</em> from count_lucky(b).</li> </ul> <p>That's all. Precalculation work for O(log(MAX_NUMBER)^3), each step have also this complexity.</p> <p>I've tested my solution against linear straightforward one and results were equal</p>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm to find Lucky Numbers
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USOleGG
    1. USOleGG
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis is a very smart solution. Unfortunately, it doesn't work 100% since you can't split every number up into powers of 10. I had a different solution which also required a similar splitting, and could find no way to split a number such as 1234567, although 1100111 will split fine into powers of 10. Most numbers split into *multiples* of powers of 10 which doesn't quite work with your table I don't think.
      singulars
      1. PO
      1. USThe111
    2. COThank you for your comment, I've really found one bug in my algo, so I've updated it. Now I've tested it on all numbers from 1 to million and results was the same with straightforward solution. Cycle `for (int l = 0; l < split_max[i]; ++l)` allows us to deal not only with numbers like 1100111, but with all - I took into account that first digit in splitted part can be no only 0 or 1.
      singulars
      1. PO
      1. USOleGG
    3. COThanks for the update. I was trying to come up with a similar mod to your algorithm myself, but yours is better. :-)
      singulars
      1. PO
      1. USThe111
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload