Jack and jones

general
,
1

Can anyone help me to solve Jack And Jones from LOC September challenge?

1 Like
2

The problem asks to find the digit_sum of unique prime factors for each number. Then over a range L to R we have to find the sum of digit_sum of all numbers from L to R.

Quick Explanation : use prime sieve

Explanation : We can precompute the sum of digit_sum of all prime factors from 1 to 1e6(max value of R) using a simple prime sieve.
How to do this ?
Here’s the process :

    for(i = 2 to 1e6)
    {
        if(!sum[i]) // i is not prime
        {
            sum[i] += sum_of_digits(i); // every prime number stores its sum_of_digits
            for(j = (2 * i) to 1e6)
                sum[j] += (sum[i]);
                j = j + i;
            //each j is a multiple of i
        }
    }
what is this doing ? 
Well, sum[i] stores the sum of all digit_sum of unique prime factors of i.. so it contains value 0 or > 0. Initially we consider all elements to be prime(sum[i] = 0 for all i). Then we start from 2 and add to all its multiples(2, 4, 6, 8, ..) its sum of digits(j is a multiple of i and we loop through all multiples of i). Next unmarked is 3, we add 3 to all multiples of 3(3, 6, 9, 12, ...). Next is 4 but it has already been marked by 2(prime[4] != 0), because its a multiple of 2. Next unmarked is 5 and again we add its sum_of_digits to all its multiples.. Likewise we iterate through each i and for every unmarked i(which is a prime number) we add its sum of digits to all its multiples.

Notice that while we iterate through i only those i’s that are prime stay unmarked, and we can easily visit all its multiples and add to them sum_of_digit(i).
Every i is an unique prime factor of every j.
Now the sum[i] array is ready, we compute the prefix sum of sum[i] in a new array prefix. prefix[i] gives us the sum of all magic_values(sum of unique prime factors) for all numbers from 0 to i.For a given range L to R, the answer is simply prefix[R] - prefix[L - 1].

Here is the link to my AC code : https://www.codechef.com/viewsolution/15555288

Hope this helps.Please feel free to comment if you dont understand any part of it.
Happy Coding !! :slight_smile:

2 Likes
3

Normal Q etc are not supposed to be marked as wiki.

4

MY SOLUTION