题解 P2312 【解方程】

· · 题解

首先要知道的是高次方程无求根公式，所以解这个方程没有公式，套公式只能过30%的数据

一种方法是枚举1到m的正整数，判断行不行。

若用高精度则只能能拿50分，那如何优化呢？取模！

设f(x)=a0+a1*x+a2*x^2+..+an*x^n

若f(x)=0则f(x) mod p=0（p为任意非0实数）

随意试几个p，若f(x) mod p都是0，那x很有可能就是方程的解

但有几点要注意：

1。p最好是质数 2。p试得越多，p越大正确率越高，但也会慢一点点，根据实际情况自己调节

如果光是这样，理论上只能过70%的数据，可能是因为洛谷评测机快吧，这样也能过

我提供一个好一点的算法

注意到当f(x) mod p=0时f(x+k*p) mod p=0（k为整数）

这样可以避免枚举很多无用的解

秦九韶算法我默认你们都会的，毕竟连读入优化都要用到这个

下面是代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=10007,q=100000007;
int n,m,i,cnt,ans[1000003],v[p],y;
ll a[103],b[103],aa,bb;
char c;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int x=0,fl=1;char ch=gc();
    for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
    for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
    return x*fl;
}
inline bool f(int p,int M,ll *t){//把p代入方程，判断模M是否为0
    ll x=t[n];
    for (int i=n-1;i>=0;i--) x=(x*p+t[i])%M;
    return x==0;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){wri(a);puts("");}
int main(){
    n=read();m=read();
    for (i=0;i<=n;i++){//读入优化
        aa=0,bb=0;
        for (c=gc(),y=0;c<48 || 57<c;c=gc()) if (c=='-') y=1;
        for (;48<=c && c<=57;c=gc()) aa=((aa<<3)+(aa<<1)+(c^48))%p,bb=((bb<<3)+(bb<<1)+(c^48))%q;
        a[i]=y?p-aa:aa;
        b[i]=y?q-bb:bb;
    }
    for (i=0;i<p;i++)
        if (f(i,p,a)) v[i]=1;
    for (i=1;i<=m;i++)
        if (v[i%p] && f(i,q,b)) ans[cnt++]=i;
    wln(cnt);
    for (i=0;i<cnt;i++) wln(ans[i]);
}

我原来的程序好像被@中二攻子hack了，虽然我本机运行出来还是对的（可能我编译器出锅了），但是我还是发现了我程序的bug，已修改