P5691 [NOI2001] 方程的解数
[NOI2001] 方程的解数
题目描述
已知一个 n n n 元高次方程:
∑ i = 1 n k i x i p i = 0 \sum\limits_{i=1}^n k_ix_i^{p_i} = 0 i=1∑nkixipi=0
其中: x 1 , x 2 , … , x n x_1, x_2, \dots ,x_n x1,x2,…,xn 是未知数, k 1 , k 2 , … , k n k_1,k_2, \dots ,k_n k1,k2,…,kn 是系数, p 1 , p 2 , … p n p_1,p_2,…p_n p1,p2,…pn 是指数。且方程中的所有数均为整数。
假设未知数 x i ∈ [ 1 , m ] ( i ∈ [ 1 , n ] ) x_i \in [1,m] \space ( i \in [1,n]) xi∈[1,m] (i∈[1,n]),求这个方程的整数解的个数。
输入格式
第一行一个正整数 n n n,表示未知数个数。
第二行一个正整数 m m m。
接下来 n n n 行,每行两个整数 k i , p i k_i,p_i ki,pi。
输出格式
输出一行一个整数,表示方程解的个数。
样例 #1
样例输入 #1
3
150
1 2
-1 2
1 2
样例输出 #1
178
提示
【数据范围】
对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 6 1\le n \le 6 1≤n≤6, 1 ≤ m ≤ 150 1\le m \le 150 1≤m≤150,且
∑ i = 1 n ∣ k i m p i ∣ < 2 31 \sum\limits_{i=1}^n |k_im^{p_i}| < 2^{31} i=1∑n∣kimpi∣<231
答案不超过 2 31 − 1 2^{31}-1 231−1, p i ∈ N ∗ p_i \in \mathbb N^* pi∈N∗。
分析
数据较小,使用折半搜索,每个搜索搜一半,先枚举出每个可能性,再查找即可
代码
#include <bits/stdc++.h>
using namespace std;
const int M = 1e7;
int n, m, tot, ans;
int b[M];
int k[10], p[10];
void read() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> k[i] >> p[i];
}
int powm(int x, int b) {if (b == 0) return 1;int res = pow(x, b >> 1);if (b % 2 == 0) return res * res;return res * res * x;
}
void dfs1(int i,int sum) {if (i > n) { b[++tot] = -sum; return; }for (int x = 1; x <= m; x++) {int t = powm(x, p[i]) * k[i];dfs1(i + 1, sum + t);}
}
void dfs2(int i, int sum) {if (i > n / 2) {int res = upper_bound(b + 1, b + 1 + tot, sum) - lower_bound(b + 1, b + 1 + tot, sum);ans += res; return;}for (int x = 1; x <= m; x++) {int t = powm(x, p[i]) * k[i];dfs2(i + 1, sum + t);}
}
int main() {read();dfs1(n / 2 + 1, 0);sort(b + 1, b + 1 + tot);dfs2(1, 0);cout << ans;return 0;
}
分析
int powm(int x, int b) {if (b == 0) return 1;int res = pow(x, b >> 1);if (b % 2 == 0) return res * res;return res * res * x;
}
由于是高次方程,可以使用快速幂优化
void dfs1(int i,int sum) {if (i > n) { b[++tot] = -sum; return; }for (int x = 1; x <= m; x++) {int t = powm(x, p[i]) * k[i];dfs1(i + 1, sum + t);}
}
由于 x ∈ [ 1 , m ] x \in [1,m] x∈[1,m],所以枚举每个x的值,算出一半的答案,记录在数组中
void dfs2(int i, int sum) {if (i > n / 2) {int res = upper_bound(b + 1, b + 1 + tot, sum) - lower_bound(b + 1, b + 1 + tot, sum);ans += res; return;}for (int x = 1; x <= m; x++) {int t = powm(x, p[i]) * k[i];dfs2(i + 1, sum + t);}
}
与dfs1基本相同,但搜索完毕后记得统计答案数,更新ans即可