15295 Fall 2020 #13 Number Theory -- Problem Discussion
November 25, 2020
This is where we collectively describe algorithms for these problems. To see the problem statements and scoreboard, go to this page and select this contest.
A. LCM
lcm(a,b) = ab/gcd(a,b), so the value we're computing is b/gcd(a,b) for values of a that go higher than b. Therefore, gcd(a,b) ranges over all divisors of b, so b/gcd(a,b) ranges over all divisors of b, so the answer is just the number of divisors of b (quickly computable via factoring b, and then take the product of each of the exponents of the primes +1).
B. Polycarp and Div 3
Employ a greedy algorithm. If in the string “abcdefgh” that “bc” is a 3 digit multiple (and neither a nor ab is), might as well take that and continue. Then, it remains to use the divisibility rule for 3.
You can also go across the sequence, keeping track of “so far, what is the best number of cuts where the last segment mod 3 is (0,1,2)”
C. Moodular Arithmetic
If k = 0 or k = 1, then the answers are p^(p - 1) and p^p, respectively. For k >= 2, observe that fixing the value of f(n) for some choice of n also fixes the values of f(k * n), f(k^2 * n), …, up until f(k^(m - 1) n), where m is the order of k in the multiplicative group modulo p. You can think of the set {n, k * n, k^2 * n, …, } as forming an equivalence class of size m (if you are familiar with group theory, this is equivalently fixing the values of f on one coset in the coset space G / <k>, where <k> is the cyclic subgroup generated by k). From here, you can see that f’s behavior on all nonzero inputs is uniquely determined by one value it takes in each equivalence class, and there are (p - 1)/m classes.
For the case of 0, substituting x = 0 into the functional equation shows that f(0) = 0. Thus the answer in this case is just p^((p - 1) / m), since we only need to pick the value of f on (p - 1)/m values to determine the rest of the values. You can find m in O(p) time just by computing successive powers of k modulo p, and waiting until you reach 1, which is fine.
D. GCD Counting
Consider the following algorithm: For each prime p, let T_p be the forest induced by the set of vertices whose values are divisible by p. If we simply take the maximum diameter of T_p over all possible choices of prime p, we will be left with the maximum answer (since any possible gcd is divisible by at least one prime, it suffices only to consider primes). We can use any linear time algorithm to find the diameter of a forest T_p. The total cost of this algorithm may seem slow (after all, we are finding the diameter of many forests), but since any particular value a_i can have at most log(a_i) prime factors, the vertex i is involved in at most log(a_i) different trees. So in fact the sum over all primes p of sizes |T_p| can be at most n * log M, where M is the maximum value in a, and this algorithm is fast enough.
E. Prefix Product Sequence
First, we know that n must itself appear at the end of the sequence, and 1 must appear at the start. Now, for composite numbers more than 4, we can show that the desired sequence cannot be constructed; if n is the product of two distinct factors (other than 1 and itself), then those two factors must appear somewhere in the sequence and after they’ve appeared the rest of the sequence would be 0; otherwise, if n is a prime power (p^k for some k), then we’d still have p^(k - 1) and p appear somewhere so this is still not possible. 4 is a special case because 2 is its only non-trivial factor. Similarly, 1 is also a special case.
Now we need to find a solution for prime values of n. The claim is that we can always find a sequence such that the prefix product sequence is of the form [1, 2, …, n - 1, 0]. To show that this works, we need to show that all numbers in our base sequence are distinct; that is, we need to show that (x + 1) / x = (y + 1)/ y mod n => x = y mod n (which we can verify is true by multiplying both sides by xy and rearranging). Note that here, “/” denotes division in this prime group - that is, 1/x refers to the inverse of x.
So we just need to compute 1, 2/1, 3/2, 4/3, … (n - 1)/(n - 2), which we can do in O(nlogn) time by computing inverses using fast exponentiation and Fermat’s little theorem, or even O(n) time by computing all inverses sequentially in one pass at the beginning.
-- Ram
We can also find a generator (according to Wikipedia one happens in the first O(log^6 n) numbers) of the multiplicative group, and then solve the problem additively instead of multiplicatively. When n is an odd prime (aka not 2---has to be a special case), the multiplicative group has even order so the sequence 0, 1, -2, 3, -4, 5, … works since the partial sums are 0, 1, -1, 2, -2, 3, -3… both of which eventually cover all numbers modulo an even number once.
-- Chris
(In the above proof that if n > 4, then n must be prime, isn’t the case n = p^2 still unproven? I guess one way to resolve this is to note that if n = ab > 4, then a + b <= ab - 1 and hence (ab - 1)! contains a * (a + 1) * … * (a + b) in its expansion. So it must be divisible by a, and also divisible by b (since any sequence of b consecutive integers must contain one multiple of b)
Yes, or alternatively we can note that p and 2p are both < p^2 in the case of p > 2, so they must appear somewhere earlier as well, and everything after that must be 0
-- Ram
F. Deleting Numbers
Note that if you ever use operation 2 on the number m, and then you use operation 1 on km for some integer k, then the result is 1 if km is a factor of x and 0 otherwise.
There are 9592 primes under 10^5. If you don’t query every prime at least once, then each unqueried prime and the number 1 are indistinguishable from each other. So we will at least have to query every prime.
In fact, the first step should be to figure out all of the prime factors of the number. Once we know which prime factors exist, the rest of the problem will be pretty easy as such: For each prime p, assuming we’ve already used operation 2 on p, then we can use operation 1 on p, p^2, p^3, etc. until our result goes from 1 to 0. This lets us get the exponent of p in the prime factorization of x. (We could use a binary search, but it’s not necessary and the iterative search is a lot easier.) After doing this for all of the primes in the factorization, we’ll know the exact prime factorization of x, so we know what x is.
It’s pretty easy to find all the prime factors if we had two queries per prime: For each prime, use a deletion, and then a query on the same number; it’s 1 if p | x and 0 otherwise. However, we barely have one query per prime.
Let’s query all the primes in order (2, 3, etc.) The first observation is that whenever we encounter a prime that isn’t the smallest prime factor of x, we can immediately learn that it is a factor of x. Create an array storing for each prime how many numbers less than n have that prime as its smallest factor (this is pretty easy with a Sieve of Eratosthenes). Then in each deletion query we would “expect” the number of multiples to be equal to that number. If it isn’t, and it’s exactly one more, then that means that x is a multiple of the prime factor that we thought was deleted earlier but isn’t.
All that remains is to figure out how to get the smallest prime factor. The final trick is to use queries of the form “A 1”. Since we know for each prime how many numbers we were expected to delete, then “A 1” queries will tell us immediately if we’ve encountered x yet or not. Then if we actually find that we have one more number still in the set than we would have expected, we can just do type-1 queries through every prime since the previous “A 1” check, to see if it is indeed a factor of x.
But how do we do this efficiently? Well, we can do this in square root-sized blocks. Split up all the primes into blocks of size 100 (roughly sqrt(9592)). At the end of each block, query “A 1” and if you see one too many numbers, you know you’ve encountered the smallest prime factor of x. This lets you find the smallest prime factor, and since we know how to find the rest of the prime factors,
Let m=pi(n) (the prime counting function); this solution uses roughly m+2*sqrt(m)+log(n) queries, which is good enough. (The number of distinct prime factors is pretty small, only 6 for N=1e5, so that’s not a factor.)
-eric