本文主要是介绍【noip】解方程 秦九韶算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
解方程
描述
已知多项式方程:
a0+a1x1+a2x2……+an−1xn−1+anxn=0
求这个方程在[1, m]内的整数解(n 和 m 均为正整数)。输入格式
输入共 n+2 行。
第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。
接下来的 n+1 行每行包含一个整数,依次为 a0,a1,a2,...,an 。输出格式
第一行输出方程在[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, | ai | ≤ 100,anan ≠ 0, m ≤ 100;
对于 50%的数据,0 < n ≤ 100,| ai | ≤ 10100 , an ≠ 0,m ≤ 100;
对于 70%的数据,0 < n ≤ 100,| ai | ≤ 1010000 , an ≠ 0,m ≤ 10000;
对于 100%的数据,0 < n ≤ 100,| ai | ≤ 1010000 , an ≠ 0,m ≤ 1000000。来源
NOIP2014 提高组 Day2
这个题一看很吓人, 1010000 ?!多大一个数啊,高精度?肯定超时.
怎么做?
先是一定要用秦九韶算法,不然写起来不仅慢还很辛苦。
秦九韶算法:
f(x)=a0+a1x1+a2x2……+an−1xn−1+anxn=a0+x(a1+x(a2+x(a3+……x(an−1+xan))…)
这样处理以后,枚举x,从内向外算就可以在O(n)验证方程,而且写起来也轻松
但是数字很大,高精度不可能
写不来set的我,天天暴力哈希,这让我直接就想到可以都同余方程,两边各模一个质数,若原方程计算结果为0,模了以后也为0,然后多取几个质数可以避免冲突。过了70%,T了30%。
也就是说还要优化。
都想到了同余方程那自然就可以想到后面的这个了: f(x)≡f(x+p)(modp)
这样我们就只用算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】解方程 秦九韶算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!