CrossPrimesOut
SRM 821 · 2022-01-07 · by misof
Problem Statement
Consider an infinite sequence of digits. For example, here's the prefix of sqrt(47), with the decimal point removed: 6855654600401044124935871449084848960460643461001326275485108185678...
Now consider a simple infinite process. During the process we maintain an infinite text. Initially, this text consists of our infinite sequence of digits. Then, for each prime, in increasing order, we do the following:
- Find the first occurrence of the prime in the current infinite text.
- If we did find it, replace it by spaces. (If the entire infinite text contains no occurrences of the current prime, nothing happens.)
After the entire infinite process is done, we are left with a collection of space-separated tokens. We convert them back into numbers to obtain the result: a sequence of non-negative integers.
You are given an
Determine and return the N-th term (0-based index) of the sequence produced by the above process if we start with the decimal expansion of sqrt(X). Return its value modulo 10^9 + 7.
Notes
- Spaces matter. For example, "1234 789" does NOT contain an occurrence of "47".
Constraints
- X will be between 1 and 10,000, inclusive.
- X will not be a square.
- N will be between 0 and 30, inclusive.
47 1 Returns: 5654600
We start with sqrt(47): 6855654600401044124935871449084848960460643461001326275485108185678... We find and remove the first 2: 68556546004010441 4935871449084848960460643461001326275485108185678... We find and remove the first 3: 68556546004010441 49 5871449084848960460643461001326275485108185678... We find and remove the first 5: 68 56546004010441 49 5871449084848960460643461001326275485108185678... Now the same with 7, 11, 13, and so on. Immediately before processing the prime 401 we have the following: 68 565460040104 49 58 144908484 604606 4 00 26275485108185 8... Removing the first occurrence of 401 produces: 68 5654600 04 49 58 144908484 604606 4 00 26275485108185 8 At this point it's easy to show that in the final sequence element 0 will be 68 and element 1 will be 5654600. Thus, we return 5654600.
47 2 Returns: 4
The final token at index 2 in the sequence for sqrt(47) is "04", as seen in the previous example. When converted into an integer, the leading zero is obviously lost.
47 9 Returns: 0
Here the actual string token produced by the infinite process is "00".
5 10 Returns: 270897077
The actual term is 24,270,897,245.
2 0 Returns: 1
Submissions are judged against all 120 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CrossPrimesOut with a public method int findTerm(int X, int N) · 120 test cases · 2 s / 256 MB per case