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 ≤ xiM for i = 1 … n. Find the number of integer solutions.

Input Format

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 Format

Output one integer - the number of integer solutions that solves the equation.

Sample Input

3
150
1 2
-1 2
1 2

Sample Output

178

Constraints

  • 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.

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: May 08, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...