传送门
思路分析
怎么求解呢?
其实我们可以把左边的式子当成一个算式来计算,从1到 $ m $ 枚举,只要结果是0,那么当前枚举到的值就是这个等式的解了。可以通过编写一个 $ bool $ 函数来判断算式的值是不是0
至于如何计算这个多项式,用秦九韶算法就可以解决
细节提示 :
1.防爆 $ int $ 常用方法:模大质数!(另:好像模一个质数有的时候会出事233可以多模几个大质数)
2.最好用上读入优化,而且边读边取模。
3 . $ sum $ 每次都要清零
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define re register
using namespace std;
const long long mod = 1000000007;
inline int read(){
char ch = getchar();
long long f = 1 , x = 0 ;
while(ch > '9' || ch < '0') {if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = ((x << 1) + (x << 3) + ch - '0') % mod ;ch = getchar();}
return x * f;
}
long long n,m,ans,cnt,sum;
bool flag = true;//用来判断是否有解
long long a[110],key[1000005];
inline bool calc(long long x) {
sum = 0 ;
for(re long long i = n ; i >= 1 ; --i) {
sum = ((a[i] + sum) * x) % mod;
}
sum = (sum + a[0]) % mod;
return !sum;
}
int main(){
n = read(); m = read();
for(re long long i = 0 ; i <= n ; ++i) {
a[i] = read();
}
for(re long long i = 1 ; i <= m ; ++i) {
if(calc(i)){
flag = false;
ans++;
key[++cnt] = i ;
}
}
if(flag) {
printf("%lld\n",ans);
return 0;
}
printf("%lld\n",ans);
for(re long long i = 1 ; i <= cnt ; ++i)
printf("%lld\n" , key[i]);
return 0;
}
洛谷P2312解方程的更多相关文章
-
洛谷P2312 解方程题解
洛谷P2312 解方程题解 题目描述 已知多项式方程: \[a_0+a_1x+a_2x^2+\cdots+a_nx^n=0\] 求这个方程在 \([1,m]\) 内的整数解(\(n\) 和 \(m\) ...
-
洛谷 P2312 解方程 解题报告
P2312 解方程 题目描述 已知多项式方程: \(a_0+a_1x+a_2x^2+\cdots+a_nx^n=0\)求这个方程在 \([1,m]\) 内的整数解(\(n\) 和 \(m\) 均为正整 ...
-
洛谷 P2312 解方程 题解
P2312 解方程 题目描述 已知多项式方程: \[a_0+a_1x+a_2x^2+\cdots+a_nx^n=0\] 求这个方程在 [1,m][1,m] 内的整数解(\(n\) 和 \(m\) 均为 ...
-
[NOIP2014] 提高组 洛谷P2312 解方程
题目描述 已知多项式方程: a0+a1x+a2x^2+..+anx^n=0 求这个方程在[1, m ] 内的整数解(n 和m 均为正整数) 输入输出格式 输入格式: 输入文件名为equation .i ...
-
洛谷 P2312 解方程
题目 首先,可以确定的是这题的做法就是暴力枚举x,然后去计算方程左边与右边是否相等. 但是noip的D2T3怎么会真的这么简单呢?卡常卡的真是熟练 你需要一些优化方法. 首先可以用秦九韶公式优化一下方 ...
-
2018.11.02 洛谷P2312 解方程(数论)
传送门 直接做肯定会TLETLETLE. 于是考验乱搞能力的时候到了. 我们随便选几个质数来checkcheckcheck合法解,如果一个数无论怎么checkcheckcheck都是合法的那么就有很大 ...
-
洛谷P2312 解方程 [noip2014] 数论
正解:数论 解题报告: 这儿是,传送门qwq 又是很妙的一道题呢,专门用来对付我这种思维僵化了的傻逼的QAQ 首先看题目的数据范围,发现a<=1010000,很大的一个数据范围了呢,那这题肯定不 ...
-
洛谷P2312解方程题解
题目 暴力能得\(30\),正解需要其他的算法操作,算法操作就是用秦九韶算法来优化. 秦九韶算法就是求多项式的值时,首先计算最内层括号内一次多项式的值,然后由内向外逐层计算一次多项式的值,然后就将求\ ...
-
洛谷P2312 解方程(暴力)
题意 题目链接 Sol 出这种题会被婊死的吧... 首先不难想到暴力判断,然后发现连读入都是个问题. 对于\(a[i]\)取模之后再判断就行了.注意判断可能会出现误差,可以多找几个模数 #includ ...
随机推荐
-
利用Photoshop修改图片以达到投稿要求
摘自:http://www.dxy.cn/bbs/thread/8602152#8602152 利用Photoshop修改图片以达到投稿要求 软件版本为Photoshop CS V8.0.1(中文版) ...
-
超简单的JNI——NDK开发教程
不好意思各位,我按照网上一些教程进行JNI开发,折腾了半天也没成功,最后自己瞎搞搞定了,其实超简单的,网上的教程应该过时了,最新版的AS就包含了NDK编译的功能,完全不用手动javah,各种包名路径的 ...
-
linux上nginx+apache 搭建 svn服务器
众所周知,nginx目前是不支持svn的,并且由于机房网络只开了80和22(ssh)端口,所以这时候就没法单独在服务器上搭建apache+svn .所以就产生了 nginx + apache + sv ...
-
spring中使用mockito
1 mockito介绍和入门 官方:https://github.com/mockito/mockito 入门: 5分钟了解Mockito http://liuzhijun.iteye.com/blo ...
-
javaee学习之servlet
一.tomcat相关知识 tomecat虚拟主机与虚拟路径 1.tomcat的应用默认放在webapps目录下面,可以将其放在其他目录分区,让tomcat进行管理吗? 答:当然可以.方法:配置虚拟目录 ...
-
JDK6的switch支持不是很好
在switch中只支持int或者枚举型值: 不支持其他类型,如String,会报错 Cannot switch on a value of type String for source level b ...
-
Nodejs笔记(一)
Node近些日子大火,看样子js大有统一前端后台的趋势... Node.js是一个事件驱动I/O服务端JavaScript环境,基于Google的V8引擎,V8引擎执行Javascript的速度快,性 ...
-
leetcode345——Reverse Vowels of a String(C++)
Write a function that takes a string as input and reverse only the vowels of a string. Example 1:Giv ...
-
SlidingMenu和ActionBarSherlock结合滑动式菜单都
https://github.com/jfeinstein10/SlidingMenu http://actionbarsherlock.com/ SlidingMenu 的demo工程引用了Acti ...
-
XML中的五个保留字符及实体引用
字符名称 字符 实体引用 和 & & 大于号 > > 小于号 < < 单引号 ‘ ' 双引号 “ " 在XML文档中,构成元素内 ...