National Olympiad in Informatics, China, 2001

Day 2, Problem 2 - Equation Solutions

Given an nth order equation:

k₁x₁^p₁ + k₂x₂^p₂ + … + k_nx_n^p_n = 0

where: x₁, x₂, … x_n are the unknowns, k₁, k₂, … k_n are the coefficients, and p₁, p₂, … p_n are the exponents. Additionally, each value in the equation is an integer.

Assume that the unknowns will satisfy 1 ≤ x_i ≤ M 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 k_i and p_i 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
• |k₁M^p₁| + |k₂M^p₂| + … + |k_nM^p_n| < 2³¹
• The number of solutions will be less than 2³¹.
• The exponents P_i (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)