当前位置: 首页 > news >正文

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=1nkixipi=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 1n6 1 ≤ m ≤ 150 1\le m \le 150 1m150,且
∑ i = 1 n ∣ k i m p i ∣ < 2 31 \sum\limits_{i=1}^n |k_im^{p_i}| < 2^{31} i=1nkimpi<231
答案不超过 2 31 − 1 2^{31}-1 2311 p i ∈ N ∗ p_i \in \mathbb N^* piN

分析

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

代码

#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即可

http://www.lryc.cn/news/104882.html

相关文章:

  • rust里用什么表示字节类型?
  • CMake简介
  • [threejs]相机与坐标
  • Qt信号与槽机制的基石-MOC详解
  • 关于单体架构缓存刷新实现方案
  • 洞悉安全现状,建设网络安全防护新体系
  • spring中怎么通过静态工厂和动态工厂获取对象以及怎么通过 FactoryBean 获取对象
  • 三元组表实现矩阵相加(数据结构)
  • ChinaJoy 2023微星雷鸟17游戏本震撼发布:搭载AMD锐龙9 7945HX首发8499元
  • 各种运算符
  • yolov3-tiny原理解析及代码分析
  • 深入了解Redis-实战篇-短信登录
  • Mysql的锁
  • 【EI/SCOPUS征稿】2023年算法、图像处理与机器视觉国际学术会议(AIPMV2023)
  • Go语言性能优化建议与pprof性能调优详解——结合博客项目实战
  • K阶斐波那契数列(数据结构)
  • 【JavaEE】博客系统前后端交互
  • Redis 简介
  • CS162 13-17 虚拟内存
  • 接口自动化测试-Jmeter+ant+jenkins实战持续集成(详细)
  • 最长连续序列——力扣128
  • uniapp app端 echarts 设置tooltip的formatter不生效问题以及解决办法
  • Spring入门-技术简介、IOC技术、Bean、DI
  • 深度学习之反向传播
  • 网络安全 Day23-mariadb数据库数据管理和备份
  • Centos7 上安装 redis-dump 和redis-load 命令
  • 【NLP PyTorch】字符级RNN循环网络模型姓氏对应国家分类(项目详解)
  • C++设计模式之责任链设计模式
  • 《Java-SE-第二十三章》之单例模式
  • 如何快速同步第三方平台数据?