PROBLEM LINK
Author: Devendra Agarwal
Tester: Sergey Kulik
Editorialist: Florin Chirica
DIFFICULTY
easy-medium
PREREQUISITES
number theory
QUICK EXPLANATION
We need to calculate f(n) / f® * f(n - r) mod M. If f® and f(n - r) would be coprime with M, then the problem could be solved by modular inverses (extended Euclid’s algorithm). Another approach is to take each prime factor P from 2 to n and for each prime factor to calculate x = maximum x such as P^x is a factor of f(n), y = maximum y such as P^y is a factor of f® and z = maximum z such as P^z is a factor of f(n - r). The result will be product of P ^ (x - y - z), for each P from 2 to n. The solution is to calculate this only on prime divisors of M. If we ignore them and calculate the expression without them, it will be coprime with M, so we can use again modular inverse.
EXPLANATION
Particular case: f(x) is coprime with M
Let’s assume for a moment that, for every 1 <= i <= N, f(i) is coprime with M. This means every f(i) allows a modular inverse. A modular inverse can be calculated by Extended Euclid’s algorithm. A modular inverse is like division for modulo M. This means, a / b mod M is equivalent by a * ModularInverse(b) mod M. We can calculate f(N) / (f® * f(N - r)) by calculating (f(N) * ModularInverse(f®) * ModularInverse(f(N - r))) mod M. Modular inverse of a number x can be calculated in O(log(x)). We can precalculate f(i) in O(N * log(N)) time: f(i) = f(i - 1) * i ^ i mod M. i ^ i can be calculated by exponentiation by squaring, since the multiplication operation is associative.
General case
The approach works only if gcd(f(i), M) = 1. Gcd between two number is defined as common factors of both numbers at the smallest power. Let M = p1 ^ q1 * p2 ^ q2 * … for gcd(f(i), M) = 1 it means that all factors p1, p2, … need to appear at power 0 in f(i). Otherwise, it a factor pi has a power at least 1, it will also have a power at least 1 in M (otherwise it won’t be in its prime factorization) so gcd(f(i), M) is at least pi.
From here we get the following approach: we define g(i) = i^i from which we erase all factors of M. For example, let M = 6 and N = 10
g(1) = 1
g(2) = 1 ( Reason removed all factors of 2)
g(3) = 1 (Reason removed all factors of 3)
g(4) = 1 (removed all factors of 2)
g(5) = 5^5
g(6) = 1
g(7) = 7^7
g(8) = 1
g(9) = 1
g(10) = 5^10 (NOTE THIS)
Let’s define g’(x) = g’(x - 1) * g(x). Now g’(x) is coprime with M. This means you can apply the approach from above.
However, the result is not complete yet. So far we have g’(N) * ModularInverse(g’(N - r)) * ModularInverse(g’®), which is the answer, EXCEPT all prime factors for M. We need to multiply this number by p1 ^ (x1 - y1 - z1) * p2 ^ (x2 - y2 - z2) * …
xi is the largest power such as pi ^ xi is a divisor of f(N).
yi is the largest power such as pi ^ yi is a divisor of f®.
zi is the largest power such as pi ^ zi is a divisor of f(N - r).
By doing this, all factors of M are multiplied to the result and we’re done. The number of factors of M is small (worst case 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 27 > 10^9). So we can afford to process each factor of M one by one. For a factor P, for each f(i), we need to calculate maximum x such as P ^ x is a divisor of f(i). The power P ^ x modulo M can be calculated then by exponentiation by squaring, too.
Number x for 1^1 * 2^2 * … * i^i is calculated in the following way: we can write each y^y number as some P^y * another number. The whole product will be P^y1 * foo * P^y2 * bar * … = P^y1 * P^y2 * … * P^yi * some_number = P^(y1+y2+…+yi) * some_number. By yi I denote maximum number such as P^yi divides only i ^ i term.
How to get P^yi such as yi is the power of P in prime decomposition of i ^ i? i can be written as a product of prime factors. We’re interested only in power of factor P. So i = (P ^ power * other_numbers) ^ i. We get that i = P ^ (power * i) * other_numbers. Hence, yi = power * i. To get power, we simply divide i by P as much as possible (of course, we need to have remainder equal to zero) and we increment power each time.
This problem allows multiple approaches. If you have a different solution, please share it with us!
Complexity
Let cnt the number of prime factors of M. Precalculation step takes O(cnt * n). For a query, modular inverse stuff takes O(log(n)) and using precalculated info by exponentiation by squaring also takes O(log(n)) time.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be updated soon
To be updated soon
