题目名称	304. [NOI 2001]方程的解数
输入输出	`equation1.in/out`
难度等级	★★☆
时间限制	3000 ms (3 s)
内存限制	128 MiB
测试数据	10
题目来源	BYVoid 于2009-03-21加入
开放分组	全部用户
提交状态
分类标签	NOI 搜索法散列
	分享题解

通过：47，提交：216，通过率：21.76%
ajcxsu	100	0.492 s	30.83 MiB	C++
alexhaoge	100	0.778 s	56.18 MiB	C++
宋逸群	100	0.936 s	18.04 MiB	C++
AAAAAAAAAA	100	0.983 s	34.69 MiB	C++
Candy？	100	1.020 s	49.92 MiB	C++
宋逸群	100	1.101 s	18.04 MiB	C++
KCkwok	100	1.391 s	85.74 MiB	C++
ZXCVBNM_1	100	1.393 s	46.15 MiB	C++
ZXCVBNM_1	100	1.412 s	53.79 MiB	C++
ZXCVBNM_1	100	1.418 s	38.89 MiB	C++

本题关联比赛
SYOI 专题 6：折半搜索

关于方程的解数的近10条评论(全部评论)
选对模数很重要不要选233333 QAQ ztx 2015-05-15 18:44 3楼
Orz 漩涡殿下！ Makazeu 2013-01-05 21:49 2楼
C++代码在COGS上运行时出错（E）有可能是超出内存限制，比如假设内存限制是64M 全局变量消耗了60M，然后有个递归的函数这个函数的系统栈需要的内存大于4M是就回爆内存，但是不提示M，是E，不小心忘了就会调好久。注意一下！ QhelDIV 2013-01-03 16:44 1楼

304. [NOI 2001]方程的解数

★★☆ 输入文件：equation1.in 输出文件：equation1.out 简单对比
时间限制：3 s 内存限制：128 MiB

问题描述

已知一个n元高次方程：

\[ k_1x_1^{p_1} + k_2x_2^{p_2} + \cdots + k_nx_n^{p_n} = 0 \]

其中：x1, x2, …,xn是未知数，k1,k2,…,kn是系数，p1,p2,…pn是指数。且方程中的所有数均为整数。

假设未知数1≤ xi ≤M, i=1,,,n，求这个方程的整数解的个数。

输入文件

文件的第1行包含一个整数n。第2行包含一个整数M。第3行到第n+2行，每行包含两个整数，分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i=1，第n+2行的数据对应i=n。

输出文件

文件仅一行，包含一个整数，表示方程的整数解的个数。

输入样例

输出样例

约束条件

1<=n<=6；1<=M<=150；

\[ |k_1M^{p_1}| + |k_2M^{p_2}| + \cdots + |k_nM^{p_n}| < 2^{31} \]

方程的整数解的个数小于2^31。

★本题中，指数Pi(i=1,2,……,n)均为正整数。