题解 P2312 【解方程】

· · 题解

NOIP2014 D2T3 解方程

题目大意：给定一个n次方程，求其在[1,m]内的整数解

0<n≤100，m<10^6

解答：

只要数学写得好，都清楚n次方程的导数，单调性，解的判断之类都是十分复杂的，而且题目要求整数解，根本无法通过数学推导的方式得出答案

那我们只能写一个 for 循环，依次判断 1到m 的每个数是否符合方程了

m<10^6，意味着每次判断的复杂度最多为O(n)，才能保证不会超时

a[i]≤10^10000？估计高精肯定遭不住了

那我们只剩下一条路：取模

通过取模性质来读入每个数，然后依次判断

不过这样的话，每次判断即使用上快速幂，也超过了O(n)的限制（大概是O(n log n)吧）

估计过不了（或者要卡常卡出花）

怎么办？

高中数学必修三上有这么一个人，叫做秦九韶（qaq）

他发明了一个著名的秦九韶公式，可以有效降低高次多项式计算的复杂度

代码不在此处展示（其实大家在写快读时都用到了他，只是没有察觉而已）

用了他，我们成功把每次判断的复杂度降到了O(n)

那么总时间复杂度就变成了O(nm)，符合题意，成功AC（撒花）

注意：

1.在大数学题中，如果无法准确掌握自己的答案和中间结果会不会溢出，

那就开 long long 吧（十年OI一场空，不写 long long 见祖宗）

2.别忘了取模，而且记得取一个大质数

（我一开始取了个1145141，结果差点爆0，换成10^9+7才成功AC）

3.快读那边，注意a[i]有可能是负数

（负数那边我也不太懂为什么只能这么取（只能面向样例编程？））

代码如下：

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,m,a[120];
vector<long long>ans;
long long read(){
    long long f=1,ans=0;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        ans=(ans*10+ch-'0')%mod;
        ch=getchar();
    }
    return f*ans;
}
bool check(long long x);
int main(){
    //读入 
    n=read(),m=read();
    for(long long i=0;i<=n;++i)
        a[i]=read();
    //枚举检验 
    for(long long i=1;i<=m;++i)
        if(check(i))ans.push_back(i);
    //输出答案 
    long long size=ans.size();
    cout<<size<<endl;
    for(long long i=0;i<size;++i)
        cout<<ans[i]<<endl;
    return 0;
}
bool check(long long x){
    long long val=0;
    for(long long i=n;i>=0;i--)
        val=(val*x+a[i])%mod;
    return val==0;
}