National Olympiad in Informatics, China, 2001
Day 2, Problem 2 - Equation Solutions
Given an nth order equation:
k1x1p1 + k2x2p2 + … + knxnpn = 0
where: x1, x2, … xn are the unknowns, k1, k2, … kn are the coefficients, and p1, p2, … pn are the exponents. Additionally, each value in the equation is an integer.
Assume that the unknowns will satisfy 1 ≤ xi ≤ M for i = 1 … n. Find the number of integer solutions.
The first line of input contains the integer n.
The second line of input contains the integer M.
Lines 3 to n+2 will each contain two space-separated integers, the values of ki and pi respectively. Line 3 corresponds to when i = 1, and line n+2 corresponds to when i = n.
Output one integer - the number of integer solutions that solves the equation.
3 150 1 2 -1 2 1 2
- 1 ≤ n ≤ 6
- 1 ≤ M ≤ 150
- |k1Mp1| + |k2Mp2| + … + |knMpn| < 231
- The number of solutions will be less than 231.
- The exponents Pi (i = 1, 2, …, n) in this problem will each be a positive integer.
Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: May 08, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3