PolynomialGCD
SRM 657 · 2015-03-26 · by rng_58
SRM 657 · 2015-03-26 · by rng_58 · Math
Problem Statement
Problem Statement
Cat Snuke has learned that the number of ways to choose three things from x identical things is x(x-1)(x-2)/6.
It means that the polynomial x(x-1)(x-2) is divisible by 6 for any integer x.
He defined the greatest common divisor (GCD) of a nonzero polynomial P as the maximal integer d such that P(x) is always divisible by d for any integer x.
For example, the GCD of P(x) = x(x-1)(x-2) is 6, because P(x) is always divisible by 6 and no bigger integer divides all P(x).
You want to compute the GCD of a polynomial P that is given as a product of many linear terms. You are given aString s that describes P.
Construct P as follows:
Start with P(x)=1 for all x.
For each valid i, the character s[i] will be between '0' and '9', inclusive.
Interpret it as a digit d[i] between 0 and 9, inclusive.
Multiply P by the term (x-i)^d[i].
Compute the GCD of the polynomial P, and return it modulo 1,000,000,007.
You want to compute the GCD of a polynomial P that is given as a product of many linear terms. You are given a
Compute the GCD of the polynomial P, and return it modulo 1,000,000,007.
Constraints
- s will contain between 1 and 10,000 characters, inclusive.
- Each character in s will be between '0' and '9', inclusive.
Examples
0)
"111" Returns: 6
P(x) = x(x-1)(x-2). The GCD of this polynomial is 6 as written in the statement.
1)
"00000" Returns: 1
P(x) = 1.
2)
"2014" Returns: 16
P(x) = (x-0)^2 * (x-1)^0 * (x-2)^1 * (x-3)^4 = x^2 * (x-2) * (x-3)^4.
3)
"31415926535" Returns: 659897170
4)
"9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999" Returns: 972408461
Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PolynomialGCD with a public method int gcd(string s) · 84 test cases · 2 s / 256 MB per case