NOIp 2014 解方程 【数学/秦九韶算法/大数取膜】By cellur925

题目传送门

题意：求高次方程的解及其个数。其中

1°

我们知道，高次方程是没有求根公式的。但是利用逆向思维，我们可以进行“试根法”，因为题目中给出了所求根的范围。但是多项式系数过于吓人，达到了sxbk的1e10000.longlong显然盛不下。只能看做字符串处理。然而即使是处理成字符串，我们也不可能真的去乘这么多。

2°

考虑取膜。我们把多项式系数进行取膜，它的相对效果和不取膜是一样的。（想一想，为什么）

除了对系数取膜，我们还可以考虑对x取膜。

3°

难道在x比较小的时候，我们计算这个多项式的值也需要暴力搞嘛？

我们智慧的先人秦九韶早就计算了一种计算多项式的简化方法，复杂度O（n）

（你可以在高中数学必修3中学到它）

它大概长这样：

它的代码大概长这样：

 bool check(int x,int mo)

 {

     ll num=;

     for(int i=n+;i>=;i--)

         num=(num*x+a[i][mo])%prime[mo];

     return num==;

 } 

于是我们就可以 快速求解多项式的值了。

至此，本题就结束了=w=。

复杂度O（TMN），T为选取模数的个数。

Code

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 int n,m,ans;

 char op[];

 int a[][];

 bool vis[];

 int prime[]={,,,,,};

 void read(int pos)

 {

     bool flag=;

     int st=;

     scanf("%s",op+);

     if(op[]=='-') flag=,st=;

     else st=;

     for(int i=st;i<=strlen(op+);i++)

         for(int j=;j<=;j++)

             a[pos][j]=(a[pos][j]*+op[i]-'')%prime[j];

     if(flag)

         for(int j=;j<=;j++)

             a[pos][j]=(prime[j]-a[pos][j])%prime[j];

 }

 bool check(int x,int mo)

 {

     ll num=;

     for(int i=n+;i>=;i--)

         num=(num*x+a[i][mo])%prime[mo];

     return num==;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n+;i++) read(i);

     for(int j=;j<=;j++)

     {

         int limit=min(prime[j]-,m);

         for(int i=;i<=limit;i++)

             if(!check(i,j))

                 for(int k=i;k<=m;k+=prime[j])

                     vis[k]=;

     }

     for(int i=;i<=m;i++)

         if(!vis[i]) ans++;

     if(!ans){printf("");return ;}

     else printf("%d\n",ans);

     for(int i=;i<=m;i++)

         if(!vis[i]) printf("%d\n",i);

     return ;

 }

*  开始交的时候脑子抽了以为1e6是100000于是愉快地RE了三个点233