P14073

方程的解数

难度 4 级 小学 算法入门 双向搜索
讨论 统计 9通过 37提交 24.3%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

已知一个 n 元高次方程:
\sum\limits_{i=1}^n k_ix_i^{p_i} = 0 其中:x_1, x_2, \dots ,x_n 是未知数,k_1,k_2, \dots ,k_n 是系数,p_1,p_2,…p_n 是指数。且方程中的所有数均为整数。

假设未知数 x_i \in [1,m] \space ( i \in [1,n]),求这个方程的整数解的个数。

输入

第一行一个正整数 n,表示未知数个数。

第二行一个正整数 m。

接下来 n 行,每行两个整数 k_i,p_i。

输出

输出一行一个整数,表示方程解的个数。

样例

样例 1
输入
3
150
1 2
-1 2
1 2
输出
178

提示

对于 100\% 的数据,1\le n \le 6,1\le m \le 150,且 \sum\limits_{i=1}^n |k_im^{p_i}| < 2^{31}

答案不超过 2^{31}-1,p_i \in \mathbb N^*\cap[0,2^{31})。

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交