【BZOJ】3751: [NOIP2014]解方程【秦九韶公式】【大整数取模技巧】
2024-10-20 13:55:00
3751: [NOIP2014]解方程
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 4856 Solved: 983
[Submit][Status][Discuss]
Description
已知多项式方程:
a0+a1*x+a2*x^2+...+an*x^n=0
求这个方程在[1,m]内的整数解(n和m均为正整数)。
Input
第一行包含2个整数n、m,每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数,依次为a0,a1,a2,...,an。
Output
第一行输出方程在[1,m]内的整数解的个数。
接下来每行一个整数,按照从小到大的顺序依次输出方程在[1,m]内的一个整数解。
Sample Input
2 10
2
-3
1
2
-3
1
Sample Output
2
1
2
1
2
HINT
对于100%的数据,0<n≤100,|ai|≤1010000,an≠0,m≤1000000。
Solution
暴力枚举即可,难点主要是读入和快速计算。
大整数读入解决方法是mod大~质数,题解大佬说mod一个可能会出问题所以有时候要mod几个~
快速计算的话就是秦九韶公式了QAQ,很好理解的,不过这道题要控制mod的次数!不然多100次都t了QAQ!
Code
#include<bits/stdc++.h>
#define LL long long
#define mod 1000000007
using namespace std; inline LL read() {
LL x = ; int t = ; char ch = getchar();
while(ch > '' || ch < '') { if(ch == '-') t = -; ch = getchar(); }
while(ch >= '' && ch <= '') { x = ((x << ) % mod + (x << ) % mod + ch - '') % mod; ch = getchar(); }
return x * t;
} LL a[];
int n, m, ans[], tot;
inline bool cal(int x) {
LL res = a[n];
for(int i = n - ; i >= ; i --)
res = (res * x % mod + a[i]);
return res == ;
} int main() {
n = read(); m = read();
for(int i = ; i <= n; i ++) a[i] = read();
for(int i = ; i <= m; i ++)
if(cal(i)) ans[++tot] = i;
printf("%d\n", tot);
for(int i = ; i <= tot; i ++)
printf("%d\n", ans[i]);
return ;
}
最新文章
- 51nod1265 四点共面
- ado.net 向sql中插入新数据的同时获取自增重的id值
- []with[[]]
- 调用Ajax返回500错误的解决方法
- RMAN duplicate from active遇到ora-17167,ora-12154
- java中dao层和service层的区别是什么?
- JSON互转
- Swift语言Storyboard教程:第一部分
- java虚拟机总结
- Java面试系列--java基础
- iOS发布证书申请
- iOS application/json上传文件等
- SQLSERVER 创建对Oracle数据库的DBlink以及查询使用
- RNA Sequencing
- Jmeter+ant+Jenkins构建接口自动化测试
- Python进阶量化交易场外篇3——最大回撤评价策略风险
- (转)MySQL慢查询日志总结
- 【本地服务器】用nodejs搭建最简单、轻量化的http server
- [20190423]oradebug peek测试脚本.txt
- View Pi's Status on WebBrowser