P5691 [NOI2001] 方程的解数

[NOI2001] 方程的解数

题目描述

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

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

输入格式

第一行一个正整数 $n$，表示未知数个数。
第二行一个正整数 $m$。
接下来 $n$ 行，每行两个整数 $k_i,p_i$。

输出格式

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

样例 #1

样例输入 #1

3
150
1 2
-1 2
1 2

样例输出 #1

178

提示

【数据范围】

对于 $100\%$ 的数据，$1\le n\le 6$，$1\le m\le 150$，且
$$\sum _{i=1}^n|k_i{m}^{p_i}|<2^{31}$$
答案不超过 $2^{31}-1$，$p_i\in {\mathbb{N}}^{\ast }$。

分析

数据较小，使用折半搜索，每个搜索搜一半，先枚举出每个可能性，再查找即可

代码

#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\in [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即可