【noip】解方程 秦九韶算法

本文主要是介绍【noip】解方程 秦九韶算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解方程

描述

已知多项式方程：
a0+a1x1+a2x2……+an−1xn−1+anxn=0 $a_0+a_1x^1+a_2x^2……+a_{n-1}x^{n-1}+a_nx^n=0$
求这个方程在[1, m]内的整数解（n 和 m 均为正整数）。

输入格式

输入共 n+2 行。
第一行包含 2 个整数 n、m，每两个整数之间用一个空格隔开。
接下来的 n+1 行每行包含一个整数，依次为$a_0,a_1,a_2,...,a_n$。

输出格式

第一行输出方程在[1, m]内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。

样例输入1

2 10
1
-2
1

样例输出1

1
1

样例输入2

2 10
2
-3
1

样例输出2

2
1
2

样例输入3

2 10
1
3
2

样例输出3

0

限制

对于 30%的数据，0 < n ≤ 2， |$a_i$| ≤ 100，anan ≠ 0， m ≤ 100；
对于 50%的数据，0 < n ≤ 100，|$a_i$| ≤ $10^{100}$ ，$a_n$ ≠ 0，m ≤ 100；
对于 70%的数据，0 < n ≤ 100，|$a_i$| ≤ $10^{10000}$，$a_n$ ≠ 0，m ≤ 10000；
对于 100%的数据，0 < n ≤ 100，|$a_i$| ≤ $10^{10000}$，$a_n$ ≠ 0，m ≤ 1000000。

来源

NOIP2014 提高组 Day2

这个题一看很吓人，$10^{10000}$？！多大一个数啊，高精度？肯定超时.
怎么做？
先是一定要用秦九韶算法，不然写起来不仅慢还很辛苦。

秦九韶算法：

$f(x)=a_0+a_1x^1+a_2x^2……+a_{n-1}x^{n-1}+a_nx^n=a_0+x(a_1+x(a_2+x(a_3+……x(a_{n-1}+xa_n))…)$
这样处理以后，枚举x，从内向外算就可以在O（n）验证方程，而且写起来也轻松
但是数字很大，高精度不可能
写不来set的我，天天暴力哈希，这让我直接就想到可以都同余方程，两边各模一个质数，若原方程计算结果为0，模了以后也为0，然后多取几个质数可以避免冲突。过了70%，T了30%。
也就是说还要优化。
都想到了同余方程那自然就可以想到后面的这个了：$f(x)\equiv f(x+p)(mod p)$
这样我们就只用算1~p而不是1~m了，p取3~5个2万左右的质数就可以避免冲突了。
代码见下，很简单，就没有写注释了。

#include<iostream>
#include<cstdio>
#include<string>
#define ll long longusing namespace std;
ll a[4][105],x,m,n,k,b[4][1000005],p[4]={0,10007,23333,11261};
int main()
{cin>>n>>m;for(int i=0;i<=n;i++){string s;cin>>s;int len=s.size(),flag=0;if(s[0]=='-')flag=1;for(int j=flag;j<len;j++){a[1][i]=(a[1][i]*10+s[j]-'0')%p[1];a[2][i]=(a[2][i]*10+s[j]-'0')%p[2];a[3][i]=(a[3][i]*10+s[j]-'0')%p[3]; }if(flag){a[1][i]=-a[1][i];a[2][i]=-a[2][i];a[3][i]=-a[3][i];}}for(int k=1;k<=3;k++){for(int i=1;i<p[k];i++){int t=a[k][n];for(int j=n-1;j>=0;j--)t=(t*i+a[k][j])%p[k];if(t==0)b[k][i]=1;}}for(int i=1;i<=m;i++){b[0][i]=1;for(int j=1;j<=3;j++)if(!b[j][i%p[j]])b[0][i]=0;}int num=0;for(int i=1;i<=m;i++)if(b[0][i])num++;cout<<num<<'\n';for(int i=1;i<=m;i++)if(b[0][i])printf("%d\n",i);return 0;
}

大概就是这个样子，如果有什么问题，或错误，请在评论区提出，谢谢。

这篇关于【noip】解方程 秦九韶算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---